You are given an array A of length N, which initially contains only 1’s.

A subarray from index L to R is termed “good” if for all pairs of elements within this range, their product is a perfect square.

You are also provided with a 2D array Queries consisting of Q queries. Each query is one of two types:

1. Type 1 (1 L R): Replace A[L] with R.
2. Type 2 (2 L R): Find the length of the longest “good” subarray within the range from L to R.

Compute the bitwise XOR of all queries of Type 2. Since the result can be large, return it modulo 109+710^9 + 7109+7.

Input Format:

• The first line contains an integer N, denoting the size of array A.
• The second line contains an integer Q, denoting the number of queries.
• The third line contains an integer Col, denoting the number of columns in Queries.
• Each subsequent line i (0 ≤ i < Q) contains Col space-separated integers describing the ith row of Queries.

Constraints:

• 1≤N,Q≤1051 \leq N, Q \leq 10^51≤N,Q≤105
• $3\le \text{Col}\le 3$
• 1≤Queries[i][j]≤1051 \leq \text{Queries}[i][j] \leq 10^51≤Queries[i][j]≤105