권수쌤과 그의 학생 Q명 이 맨해튼으로 수학여행을 왔습니다. 하지만 학생들이 도망쳐 시내를 자유롭게 돌아다니고 있습니다! 맨해튼은 너무 커서 N개의 도로들이 x-y 평면에 무한히 뻗어 있지만, 다행히 모든 도로는 완벽하게 수평 또는 수직으로 되어 있습니다. 각 수평 및 수직 도로는 y = c_i 또는 x = c_i 형태의 방정식으로 모델링할 수 있다.

권수쌤은 각 학생이 어디서부터 걷기 시작했는지, 그리고 얼마나 오래 전에 도망쳤는지를 정확히 알고 있습니다. 학생들은 매우 예측 가능하여 다음과 같은 패턴에 따라 걷습니다:

학생들은 북쪽(+y) 또는 동쪽(+x)으로 초당 1단위씩만 걷습니다.
현재 한 도로에 있다면, 그 도로의 방향을 따라 계속 걷습니다.
두 도로의 교차점에 있는 경우, 짝수 초 동안 걸은 후에는 북쪽으로 걷고, 홀수 초 동안 걸은 후에는 동쪽으로 걷습니다.

맨해튼의 도로 배치와 각 학생의 정보를 바탕으로 권수쌤이 현재 학생들이 어디에 있는지 알아낼 수 있도록 도와주세요!

#6219 upload 129 done 5 how_to_reg 4 call_split Subtask

맨해튼 수학여행 timer 2s memory 1024MB

#6219
Subtask

맨해튼 수학여행 2s 1024MB