포탈

교준이는 게임을 하나 개발하고 있다. 이 게임은 원형으로 배치된 $N$ 개의 방에서 진행된다. 편의상 방에 $1$번부터 $N$번까지 번호가 매겨져 있다.

방이 원형으로 배치되었다는 것은 $1$번 방에서 $2$번 방으로 이동할 수 있고, $2$번 방에서 $3$번 방으로 이동할 수 있고, ..., $N$번 방에서 $1$번 방으로 이동할 수 있음을 의미한다. 여기서, 반대의 방향으로 이동할 수 없음에 유의하라.

각 방에는 포탈이 있고, 포탈에는 하나의 정수 값이 설정되어 있다. 플레이어는 값 $X$가 설정된 임의의 포탈에서 시작하고, 값 $0$이 설정된 포탈에서 탈출할 수 있다. $X$와 $0$이 아닌 다른 값이 설정된 포탈은 비활성화되어 아무런 효과가 없다.

플레이어가 하나의 방에서 시작해 탈출하기 위해 반드시 필요한 이동 횟수를 난이도라고 정의하자.

교준이는 게임의 초기 맵을 만들어 두고, 적절히 수정해 가면서 난이도를 파악하려고 한다. 교준이를 도와 게임의 초기 맵과 맵을 수정한 과정이 주어졌을 때, 난이도를 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 맵에 있는 방의 수를 나타내는 정수 $N$, 플레이어가 시작하는 포탈에 설정된 값을 나타내는 정수 $X$, 교준이가 맵을 수정한 횟수를 나타내는 정수 $Q$가 공백으로 구분되어 주어진다. ($2 \le N \le 100\,000$; $1 \le X \le 1\,000\,000\,000$; $0 \le Q \le 100\,000$)

그다음 줄에 $N$ 개의 음이 아닌 정수가 공백으로 구분되어 주어진다. 이중 $i$ 번째 정수는 $i$ 번 방에 있는 포탈에 설정된 값을 의미한다. 이 정수는 $1\,000\,000\,000$보다 크지 않다.

이어지는 $Q$ 개의 줄의 $j$ 번째 줄에는 $j$ 번째로 맵을 수정한 정보를 나타내는 두 정수 $p_j$, $v_j$가 공백으로 구분되어 주어진다. 이는 $p_j$번 방에 있는 포탈에 설정된 값을 $v_j$로 수정했음을 의미한다. ($1 \le p_j \le N$; $1 \le v_j \le 1\,000\,000\,000$)

교준이가 맵을 수정할 때, 값이 $0$인 포탈이 새로 생기거나, 없어지지 않는다. 그리고 초기에 설정된 값이 $0$인 포탈은 반드시 한 개 이상 존재하며, 마찬가지로 한 개 이상의 포탈은 설정된 값이 $0$이 아니다.

출력 형식

$Q+1$ 개의 줄에 걸쳐 답을 출력한다. 첫 줄에 초기 맵에 대한 난이도를 출력한다. $i+1$ 번째 줄에 $i$ 번째 수정까지 반영된 이후의 맵에 대한 난이도를 출력한다.

난이도는 플레이어가 시작할 수 있는 모든 방에 대해 계산해야 하며, 그중 최댓값, 최솟값, 그리고 모든 난이도 값을 XOR 한 결과를 공백으로 구분하여 출력한다.

단, 플레이어가 시작할 수 있는 방이 하나도 없는 경우는 0 0 0을 출력한다.

예제 1

5 3 4
3 4 0 3 1
2 3
1 1
5 3
4 4

4 2 6
4 1 7
4 1 5
4 1 6
3 1 2

예제 2

5 2 1
2 0 4 2 0
3 2

1 1 0
2 1 2

예제 설명

예제 1에서, 초기 맵에서 플레이어가 시작할 수 있는 모든 방에 대한 난이도는 $2$와 $4$이다. 따라서 이 경우 4 2 6을 출력한다.

첫 번째 수정이 반영된 이후, 각 방의 포탈에 설정된 값은 $3$, $3$, $0$, $3$, $1$이 된다.

따라서 플레이어가 시작할 수 있는 방은 $3$개이다. 이때, 각 방에 대한 난이도는 $2$, $1$, $4$이다. 따라서 이 경우 4 1 7을 출력한다.

노트

제출 가능한 모든 언어에서 두 정수 a와 b의 XOR은 a ^ b로 계산할 수 있다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설