32352번 - 우-주 양궁

문제

2024 파리 올림픽에서 양궁 결승을 본 숏켁은 감격에 겨워 자신만의 양궁 게임을 만들기로 했다. 특이한 점은, 우주를 배경으로 하기 때문에 화살이 직선으로 날아간다는 점이다. 숏켁이 만든 게임에서 화살과 과녁의 충돌 판정은 다음과 같다.

1. 화살과 과녁의 충돌 판정은 매 프레임에 진행된다.
2. 화살과 과녁은 각각 좌표축과 평행하게 위치된 직육면체로 정의된다.
3. 화살과 과녁의 직육면체 내부가 겹치는 부피가 0ドル$보다 크다면, 충돌한 것으로 간주한다 (따라서 면끼리 만나는 것은 충돌하지 않은 것이다).

중력을 받지 않은 화살은 프레임 번호가 1ドル$ 증가할 때마다 $z$가 1ドル$씩 감소하도록 움직이며, 과녁은 자리에 고정되어 있다.

코드를 2ドル$번까지 작성한 숏켁은 사격 결승전을 보러 떠나버렸다. 여러분이 대신 게임을 완성시켜주자!

입력

첫 번째 줄에 화살 직육면체를 정의하는 6ドル$개의 정수 $X_{lo}, X_{hi}, Y_{lo}, Y_{hi}, Z_{lo}, Z_{hi}$가 공백으로 구분되어 주어진다. 이는 화살 직육면체가 $x$좌표가 $X_{lo}$ 이상 $X_{hi}$ 이하, $y$좌표가 $Y_{lo}$ 이상 $Y_{hi}$ 이하, $z$좌표가 $Z_{lo}$ 이상 $Z_{{hi}}$ 이하인 영역으로 이루어져있다는 것을 의미한다. $(-10^9 \le X_{lo} < X_{hi} \le 10^9;$ $-10^9 \le Y_{lo} < Y_{hi} \le 10^9;$ $0 \le Z_{lo} < Z_{hi} \le 10^9)$

두 번째 줄에 과녁 직육면체를 정의하는 6ドル$개의 정수 $x_{lo}, x_{hi}, y_{lo}, y_{hi}, z_{lo}, z_{hi}$가 공백으로 구분되어 주어진다. 이는 과녁 직육면체가 $x$좌표가 $x_{lo}$ 이상 $x_{hi}$ 이하, $y$좌표가 $y_{lo}$ 이상 $y_{hi}$ 이하, $z$좌표가 $z_{lo}$ 이상 $z_{{hi}}$ 이하인 영역으로 이루어져있다는 것을 의미한다. $(-10^9 \le x_{lo} < x_{hi} \le 10^9;$ $-10^9 \le y_{lo} < y_{hi} \le 10^9;$ $-10^9 \le z_{lo} < z_{hi} \le 0)$

모든 직육면체는 0ドル$번 프레임 시점의 좌표로 주어진다.

출력

화살과 과녁이 최초로 충돌하는 것이 몇 번 프레임인지 출력하여라. 화살과 과녁이 충돌하지 않는다면, $-1$을 출력하여라.

제한

힌트