공 이동 시뮬레이션 timer 1s memory 128MB

n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.

• 열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))

• 열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))

• 행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))

• 행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))

단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다. 예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때 query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다. (격자의 크기가 5행 × 4열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)

제한사항

• 1 ≤ n ≤ 10⁹

• 1 ≤ m ≤ 10⁹

• 0 ≤ x < n

• 0 ≤ y < m

• 1 ≤ q(=쿼리의 수) ≤ 200,000