이진 문자열

0과 1로만 이루어진 길이 $n$의 이진 문자열 $S$가 주어진다.

$S$의 인덱스는 1부터 시작하며, $S[a : b]$는 $S$에서 인덱스 $a$ 이상 $b$ 이하의 부분 문자열을 뜻한다.

다음 삽입 연산을 $m$번 적용한다. 각 연산은 정수 두 개 $x \le y$를 받으며, 연산마다 $x$와 $y$의 값은 다를 수 있다.

• 삽입할 문자열은 $S[x : y]$의 0과 1을 뒤집은 것이다. 즉, 0은 1로, 1은 0으로 바꾼다.
• 이 문자열은 $S$의 $y$번째 문자 바로 뒤에 삽입한다. 삽입 후 $S$의 길이는 $y - x + 1$만큼 늘어난다.
• 연산마다 $S$가 갱신된다. 다음 연산은 갱신된 $S$를 사용한다.

목표는 $m$번의 연산을 모두 적용한 최종 $S$의 처음 $k$글자를 구하는 것이다.

예를 들어 $S = 01010110$, $n = 8$, $m = 2$, $k = 12$이고, 연산 $(x = 2, y = 4)$와 $(x = 3, y = 5)$를 순서대로 적용한다고 하자. 첫 번째 연산은 $S[2 : 4] = 101$을 뒤집은 $101$의 반대인 010을 삽입하여 S = 01010100110을 만든다(굵은 부분이 삽입된 부분이다). 두 번째 연산은 $S[3 : 5] = 010$을 뒤집은 101을 삽입하여 S = 01010101100110을 만든다. $k = 12$이므로 답은 처음 12글자인 010101011001이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 10$).

각 테스트 케이스의 첫 줄에는 $n$, $m$, $k$가 공백으로 구분되어 주어진다.

둘째 줄에는 길이가 $n$인 문자열이 주어지며, 각 문자는 0 또는 1이다.

다음 $m$개의 줄에는 각각 정수 $x_i$, $y_i$가 주어진다. 입력은 항상 $1 \le x_i \le y_i \le$ min(i번째 연산을 적용하기 직전 $S$의 길이, $10^{12}$)을 만족한다.

또한 $k$는 $m$번의 연산을 모두 적용한 뒤 얻은 $S$의 길이와 $10^6$ 중 작은 값을 넘지 않는다.

각 테스트 케이스마다 길이 $k$인 문자열을 한 줄에 출력한다.

• 케이스 2: 1010은 10010이 된다. $k = 4$이므로 처음 4자리만 출력한다.
• 케이스 3: 10101100은 1001101100이 되고, 이어서 10011011110010000이 된다. $k = 16$이므로 처음 16자리만 출력한다.