Problem Description

You are given a array with N nodes. The array nodes are numbered from 1 to N ( represented by a_i ). In the start, the color
of any node in the array is white or black. We define that the "distance" between a and b is min{a_i| a<=i<=b} if a-th and bth
nodes have diffrerent color, or infinite if they have the same color.
We will ask you to perfrom some instructions of the following form:
0 i : change the color of the i-th node (from white to black, or from black to white);
or
1 : ask for the kinds of diffrent pair of nodes' distance is less than K

Input

The first line contains a positive integer: the number of test cases, at most 100.
After that per test case:
One line with three integers N, m and K (1 ≤ N, m ≤ 1 00000, K ≤ 1000000): the length of the array, the number of
instructions and K which used in operation 1 .
Then comes a line with N intergers a_i (|a_i|<10000000).
A line with N intergers c_i (c_i = 0(white) or 1(black)), which reprsent the color of N nodes.
Next m lines, each will be a instruction described above.

Output

one interger for each operation 1.

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

5
6