You are given an array $$A$$ consisting of $$N$$ positive integers. You are also given $$Q$$ queries of the following type:
- $$\text{1 L R X}$$: Perform $$A[i] = X$$ for all $$L \leq i \leq R$$
- $$\text{2 L R K}$$: Consider the numbers in the range $$[L..R]$$ (inclusive). Find the bitwise XOR of all possible non-empty subsets (individually) of these numbers and insert them in a set $$S$$ (equivalently remove duplicates). Also, remove the element $$0$$ from $$S$$ if it is present. Next, consider all subsets of $$S$$ of size at most $$K$$ and calculate the sum of numbers overall these subsets. The sum can be very large, output it modulo $$1000000007$$ $$(10^9 + 7)$$.
You are given $$T$$ test cases.
Warning: Use fast I/O Methods.
Input format
- The first line contains a single integer $$T$$ denoting the number of test cases.
- For each test case:
- The first line contains a single integer $$N$$ denoting the length of the array.
- The second line contains $$N$$ space-separated integers denoting the integer array $$A$$.
- The third line contains an integer $$Q$$ denoting the number of queries.
- $$Q$$ lines follow. Each line is a query of the type $$\text{1 L R X}$$ or $$\text{2 L R K}$$.
Output format
For each test case (in a separate line), print the answers corresponding to the queries $$\text{2 L R K}$$ in a single line.
Constraints
$$ 1 \le T \le 1000 \\
1 \le N \le 4 \times 10^5 \\
1 \le A_i < 2^{20} \\
1 \le Q \le 10^5 \\
1 \le L \le R \le N \\
1\le X < 2^{20} \\
1 \le K \le 10^9 \\
\text{Sum of N over all test cases does not exceed } 4 \times 10^5 \\
\text{Sum of Q over all test cases does not exceed } 10^5 \\
\text{There is atleast one query of the type 2 L R K in each test case} $$
2 4 4 2 3 1 3 2 1 2 1 1 2 3 5 2 1 2 2 3 2 1 1 1 2 1 3 2
12 30 18
In the first test case, we have $$N = 4, A = [4, 2, 3, 1], Q = 3$$. Let's look at the queries:
- $$\text{2 1 2 1}$$ :
- Consider numbers in range $$[1, 2]$$, they are $$\{4, 2\}$$.
- All non empty subsets of these numbers are $$\{4\}, \{2\}, \{4, 2\}$$.
- Bitwise XOR of all these subsets(individually) are $$4, 2, 6$$. Therefore, $$S = \{4, 2, 6\}$$.
- We have $$K = 1$$. All non-empty subsets of $$S$$ of size atmost $$K = 1$$ are $$\{4\}, \{2\}, \{6\}$$ and their sum is $$4 + 2 + 6 = 12$$.
- $$\text{1 2 3 5}$$ : Array $$A$$ becomes $$[4, 5, 5, 1]$$.
- $$\text{2 1 2 2}$$ :
- Consider numbers in range $$[1, 2]$$, they are $$\{4, 5\}$$.
- All non empty subsets of these numbers are $$\{4\}, \{5\}, \{4, 5\}$$.
- Bitwise XOR of all these subsets(individually) are $$4, 5, 1$$. Therefore, $$S = \{4, 5, 1\}$$.
- We have $$K = 2$$. All non-empty subsets of $$S$$ of size atmost $$K = 2$$ are $$\{4\}, \{5\}, \{1\}, \{4, 5\}, \{4, 1\}, \{5, 1\}$$ and their sum is $$4 + 5 + 1 + 9 + 5 + 6 = 30$$.
- Note that we output answers in a single line.
In the second test case, we have $$N = 3, A = [2, 1, 1], Q = 1$$. Let's look at the queries:
- $$\text{2 1 3 2}$$ :
- Consider numbers in range $$[1, 3]$$, they are $$\{2, 1, 1\}$$.
- All non empty subsets of these numbers are $$\{2\}, \{1\}, \{1\}, \{2, 1\}, \{2, 1\}, \{1, 1\}, \{2, 1, 1\}$$. Note that if there are same numbers we count them multiple times.
- Bitwise XOR of all these subsets(individually) are $$2, 1, 1, 3, 3, 0, 2$$. Therefore, $$S = \{2, 1, 3\}$$. Remember that in S, we need to insert only distinct values and remove the element 0.
- We have $$K = 2$$. All non-empty subsets of $$S$$ of size atmost $$K = 2$$ are $$\{2\}, \{1\}, \{3\}, \{2, 1\}, \{1, 3\}, \{2, 3\}$$ and their sum is $$2 + 1 + 3 + 3 + 4 + 5 = 18$$.
- Note that we output answers in a single line.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor