레이더

사진 제공: alex.ch

바다 한가운데에서 배의 연료가 바닥난 뒤, 당신은 80일 동안 해류를 따라 표류해 왔다. 오늘 마침내 레이더 장비를 작동시키는 데 성공했다. 그리고 신호가 수신되고 있다!

안타깝게도 신호는 별난 등대지기 Hasse가 소유한 ``radar'' 기지에서 온다. Hasse의 레이더 기지는 (다른 레이더 기지들과는 작동 방식이 조금 다르며) 서로 다른 세 파장의 연속 신호를 방출한다. 따라서 측정할 수 있는 유일하게 유용한 정보는 신호가 당신에게 도달할 때의 위상이다. 예를 들어, 맞춘 신호의 파장이 $100$미터이고 기지로부터 $1456$미터 떨어져 있다면, 장비로는 등대로부터 $56$, 또는 $156$, 또는 $256$, 또는 $\dots$미터 떨어져 있다는 것만 알 수 있다.

그래서 계산을 시작하려고 마지막 남은 종이를 꺼내지만, 잠깐, 문제가 하나 있다! 화면에는 ``ACCURACY: 3 METERS''라고 표시되어 있다. 따라서 실제로 이 신호에서 얻는 정보는 Hasse의 레이더 기지까지의 거리가 구간들의 합집합 $[53,59] \cup [153, 159] \cup [253, 259] \cup \dots$에 속한다는 것이다.

어떻게 해야 할까? 바다에서 생존하는 비결은 낙관적인 태도이므로, 세 신호에 해당하는 파장, 측정값, 정확도가 주어졌을 때 등대까지의 가능한 거리 중 최솟값이 얼마인지 알고 싶다.

해야 할 일

세 양의 소수 $m_1$, $m_2$, $m_3$ (파장), 세 음이 아닌 정수 $x_1$, $x_2$, $x_3$ (측정값), 그리고 세 음이 아닌 정수 $y_1$, $y_2$, $y_3$ (정확도)가 주어질 때, 각 $i = 1,2,3$에 대해 $z$이 $m_i$을 법으로 하여 $x_i$로부터 거리 $y_i$ 이내가 되도록 하는 가장 작은 음이 아닌 정수 $z$ (가능한 거리의 최솟값)을 구한다. 정수 $x'$이 $m$을 법으로 하여 $x$로부터 거리 $y$ 이내라는 것은, $x \equiv x' + t \pmod{m}$이고 $|t| \leq y$인 어떤 정수 $t$이 존재한다는 뜻이다.

입력은 세 줄로 주어진다. 첫째 줄은 $m_1$ $m_2$ $m_3$, 둘째 줄은 $x_1$ $x_2$ $x_3$, 셋째 줄은 $y_1$ $y_2$ $y_3$이다. 각 $i$에 대해 $0 < m_i \leq 10^6$, $0 \leq x_i < m_i$, $0 \leq y_i \leq 300$임을 가정해도 좋다. 수 $m_1$, $m_2$, $m_3$는 모두 소수이며 서로 다르다.

정답 $z$을 한 줄에 출력한다. 정답이 32비트 정수에 들어맞지 않을 수도 있음에 유의한다.