31865번 - 수열 만들기

문제

수열을 좋아하는 수민이는 1ドル$부터 $N$까지의 정수로 수열을 만들려고 한다.

수열은 다음과 같은 규칙으로 만들려고 한다.

1. 원형으로 $N$개의 자리가 있고 1ドル$은 미리 하나의 자리에 채워 넣는다.
2. 2ドル$부터 $N$까지의 수를 차례로 3번~4번 과정을 반복하며 채워 넣는다.
3. 이미 놓인 수 중 하나를 골라 $p_i$로 정하고 1ドル$ 이상 10ドル^9$ 이하의 정수 중 하나를 골라 $x_i$로 정한다.
4. $p_i$가 써진 자리를 기준으로, 시계방향으로 돌았을 때 $x_i$번째 등장하는 빈자리를 찾아 그 자리에 수를 쓴다.
5. 1ドル$이 쓰인 자리부터 시계방향으로, 차례로 자리에 적힌 $N$개의 수로 수열을 만든다.

입력

수열의 크기 정수 $N$이 첫째 줄에 주어진다. $(2 \leq N \leq 300,000円)$

둘째 줄부터 $N$째 줄까지 기준이 되는 정수 $p_i$와 이동해야 하는 칸 $x_i$가 $i$번째 줄에 주어진다. $(1 \leq p_i \leq i - 1$; 1ドル \leq x_i \leq 10^9$)

즉, $p_i$가 적힌 자리로부터 시계방향으로 돌았을 때 $x_i$번째 등장하는 빈자리에 수 $i$를 적는다는 의미이다.

출력

$N$개의 줄에 걸쳐 $i$번째 줄에 수열의 $i$번째 수를 출력한다.

제한

힌트