You are given an array A of length N, which initially contains of only 1's.
We call the subarray from L to R good, if for all pairs of elements in this range
have product as a perfect square.
You are also given a 2D array Queries which consists of Q queries. Each query is
one of the two types:
Q • Type 1-1 LR: Replace A[L] with R.
* Type 2 - 2 LR: Find the length of the longest good subarray contained in the
range from L to R.
Find the bitwise XOR of all queries of Type 2. Since the answer can be very large,
return it modulo 10pow9+7.
Input Format
The first line contains an integer. N. denoting the size of array A
The next line contains an integer, Q. denoting the number of rows in Queries.
The next line contains an integer, Col, denoting the number of columns in Queries
Each ime i of the Q subsequent lines (where 0 <= i < Q ) contains Col space
separated integers each describing the row Queries[i].
Constraints
1 <= N <= 10 ^ 5
1 <= Q <= 10 ^ 5
3 <= col <= 3
1 <= Queries[i][j] <= 10^5
Sample Test Cases
Case 1
Input:
5
5
3
213
211
111
112
222
Output:
3
Q
Explanation:
Given M = 5 Q = 5 three = 3, Q = I[2] 1, 3], [2, 1, 1], [1, 1, 1], [1, 1, 2], [2, 2, 2]].
After ist Query A = [1, 1, 1, 1, 1] , then length of longest good subarray in range [1,
3] is equal to 3.
After 2nd Query A = [1, 1, 1, 1, 1] , the length of the longest good subarray in range
[1, 1] is equal to 1.
After 3rd Query A = [1, 1, 1, 1, 1]
After 4th Query A = [2, 1, 1, 1, 1]
After 5th Query A = [2, 1, 1, 1, 1] , the length of the longest good suharray in range
12. 21 is equal to 1.
The bitwise xon of answers of queries of type 2 is equal to 1 xom 1 XOR 11.
Case 2
Input
5
5
3
211
1164
12 64
215
Output
7
Q
Case
Input
Explanation
Given N5, Q5, three 1, Q ||2. 1, 3], [2, 1, 1], [1, 1, 64], [1, 2, 64], [2, 1, 5]].
After 1st Query A [1, 1, 1, 1, 1], then length of longest good subarray in range [1, 3]
is equal to 3.
After 2nd Query A [1, 1, 1, 1, 1, the
After 2nd Query A = [1, 1, 1, 1, 1] the length of the longest good subarray in range
[1, 1] is equal to 1.
After 3rd Query A = [64, 1, 1, 1, 1]
After 4th Query A = [64, 64, 1, 1, 1] .
After 5th Query A = [64, 64, 1, 1, 1] the length of the longest good subarray in
range [1, 5] is equal to 5.
The bitwise XOR of answers of queries of type 2 is equal to 3 XOR 1 XOR 5 7.
Case 3
Input
3
5
3
112
132
213
212
223
Output:
1
Explanation:
Given N = 3, Q5, three = 3, Q = [[1, 1, 2], [1, 3, 2], [2, 1, 3], [2,, 2], [2, 2, 3]].
After the first 2 queries, the array is [2, 1, 2], and the answer's are: 1, 1, 1 and their
xor is 1.
def get(N,Q,Col, Queries)
