로봇

로봇 제작자 다우밀라스는 로봇 $M$대를 만들어 원형 경기장에서 시험하려고 합니다. 경기장은 $N$개의 구역으로 나뉘어 시계 방향으로 $1$번부터 $N$번까지 차례로 번호가 매겨져 있습니다. $1 \le i \le N-1$인 $i$번 구역은 $i+1$번 구역과 인접하고, $N$번 구역은 추가로 $1$번 구역과 인접합니다.

각 구역은 비워 두거나, 로봇 하나 또는 벽 하나를 놓을 수 있습니다(둘 다는 불가능). 다우밀라스는 $i$번 로봇에 명령 $a_i$를 입력합니다. 그런 다음 모든 로봇이 동시에 움직이기 시작합니다. $i$번 로봇은 $a_i$초 동안 초당 한 구역의 일정한 속도로 시계 방향으로 이동합니다. 진행 경로에 멈춰 있는 로봇이 있으면 속도를 늦추지 않고 그 로봇들을 앞으로 밀어냅니다. 로봇은 명령이 끝나기 전(즉 $a_i$초가 다 지나기 전)에는, 자신 또는 자신이 밀고 있는 로봇이 벽에 부딪혔을 때에만 멈춥니다. 한 구역에는 로봇이 하나만 들어갈 수 있으며, 로봇끼리 서로 지나칠 수 없습니다.

시뮬레이션이 끝났을 때 각 로봇이 어느 구역에 있게 되는지 구하세요.

첫째 줄에 정수 $N$, $M$, $K$가 주어집니다. 각각 구역의 수, 로봇의 수, 벽의 수입니다.

다음 $M$개의 줄에는 각각 두 정수 $x_i$와 $a_i$가 주어집니다. $i$번 로봇의 시작 구역과 명령입니다.

마지막 줄에는 $K$개의 정수 $y_i$가 주어집니다. 각 벽이 있는 구역입니다($K = 0$이면 이 줄은 비어 있습니다).

로봇과 벽은 각각 구역 번호가 증가하는 순서로 주어지며, 주어진 모든 구역 번호는 서로 다릅니다.

한 줄에 $M$개의 정수를 공백으로 구분하여 출력합니다. $i$번째 정수는 시뮬레이션이 끝났을 때 (입력에 주어진 순서대로) $i$번 로봇이 있는 구역 번호입니다.

• $3 \le N \le 10^9$
• $1 \le M \le 2 \cdot 10^5$
• $0 \le K \le 2 \cdot 10^5$
• $M + K \le N$
• $0 \le a_i \le N - 1$
• $1 \le x_i, y_i \le N$
• 로봇은 시작 구역이 증가하는 순서로 주어집니다.
• 벽은 구역 번호가 증가하는 순서로 주어집니다.
• 어떤 구역에도 물체(벽 또는 로봇)가 둘 이상 놓이지 않습니다.