가장 영향력 있는 호박

해그리드의 정원에 있는 호박이 살아 움직인다. 걷고, 말하고, 연애도 하고, 당연히 대표 호박을 뽑는 선거도 연다. 누가 뽑힐지는 어렵지 않게 알 수 있다. 호박을 크기 순으로 한 줄로 세웠을 때 정확히 가운데에 선 호박이 대표 호박이 된다.

해그리드는 정원이 시끄러워지는 것을 원하지 않아서 대표 호박이 누구인지 알고 싶어 한다. 크기가 같은 호박이 여럿이면 그중 누가 대표인지까지는 알 수 없지만, 대표 호박의 크기만 알아도 괜찮다.

호박은 정원에 한 줄로 자라며 1번부터 $N$번까지 번호가 붙어 있다. 해그리드는 나란히 자라는 호박에 자주 물을 준다. 두 수 $S$와 $T$를 고른 다음 $S$번 호박부터 $T$번 호박까지 전부 물을 주는 식이다. 물을 받은 호박은 크기가 정확히 1만큼 자란다. 물을 준 뒤에는 선거를 다시 하므로 대표 호박의 크기도 달라진다. 해그리드가 물을 줄 때마다 대표 호박의 크기를 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에 두 정수 $N$과 $K$가 주어진다 ($1 \le N, K \le 60000$). $N$은 항상 홀수이다.

다음 줄에는 호박의 처음 크기를 나타내는 정수 $A_i$가 $N$개 주어진다 ($1 \le A_i \le 10^9$).

이어지는 $K$개 줄에는 두 정수 $S_i$와 $T_i$가 주어진다 ($1 \le S_i \le T_i \le N$). 해그리드가 $S_i$번 호박부터 $T_i$번 호박까지 물을 주었다는 뜻이다.

모든 테스트 케이스의 $N$의 합은 60000을 넘지 않고, $K$의 합도 60000을 넘지 않는다.

입력의 마지막 줄에는 0이 두 개 주어진다. 이 줄은 테스트 케이스가 아니므로 처리하지 않는다.

각 테스트 케이스마다 $K$개 줄을 출력한다. $i$번째 줄에는 $i$번째로 물을 준 직후 대표 호박의 크기를 출력한다. $N$이 홀수이므로 이는 크기 순으로 정렬했을 때 $(N+1)/2$번째 호박의 크기와 같다.