Farmer John의 소 $N$마리($1\le N\le 10^5$)가 한 줄로 서 있다. 각 $1\le i\le N$에 대해 왼쪽에서 $i$번째 소의 번호는 $i$이다.

Farmer John은 새 아침 운동을 생각했다. 소들에게 정수 쌍 $(L_1,R_1) \ldots (L_M, R_M)$를 $M$개 주었다($1 \leq M \leq 100$). 다음 $M$단계 과정을 정확히 $K$번 반복하라고 한다($1\le K\le 10^9$).

• $1$부터 $M$까지의 각 $i$에 대해:
• 현재 왼쪽에서 $L_i \ldots R_i$ 위치에 있는 소들의 순서를 뒤집는다.

과정을 정확히 $K$번 반복한 뒤, 각 $1\le i\le N$에 대해 왼쪽에서 $i$번째 소의 번호를 출력하여라.

입력

첫 줄에 $N$, $M$, $K$가 주어진다. 각 $1\le i\le M$에 대해 $i+1$번째 줄에 $L_i$와 $R_i$가 주어지며, 둘 다 $1 \ldots N$ 범위의 정수이고 $L_i < R_i$이다.

출력

출력의 $i$번째 줄에 명령열을 $K$번 실행한 뒤 배열의 $i$번째 원소를 출력한다.

예제

입력 1

7 2 2
2 5
3 7

출력 1

1
2
4
3
5
7
6

참고

처음 왼쪽부터 순서는 $[1,2,3,4,5,6,7]$이다. 첫 단계 후 $[1,5,4,3,2,6,7]$, 두 번째 단계 후 $[1,5,7,6,2,3,4]$이다. 두 단계를 한 번 더 실행하면 예제 출력이 된다.

서브태스크

• 테스트 케이스 2는 $N=K=100$을 만족한다.
• 테스트 케이스 3-5는 $K\le 10^3$을 만족한다.
• 테스트 케이스 6-10에는 추가 제한이 없다.

문제 작성자: Brian Dean