Codeforces Round 895 (Div. 3) |
---|
Finished |
You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$, as well as a binary string$$$^{\dagger}$$$ $$$s$$$ consisting of $$$n$$$ characters.
Augustin is a big fan of data structures. Therefore, he asked you to implement a data structure that can answer $$$q$$$ queries. There are two types of queries:
Please help Augustin to answer all the queries!
For example, if $$$n = 4$$$, $$$a = [1, 2, 3, 6]$$$, $$$s = \texttt{1001}$$$, consider the following series of queries:
$$$^{\dagger}$$$ A binary string is a string containing only characters $$$\texttt{0}$$$ or $$$\texttt{1}$$$.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.
The descriptions of the test cases follow.
The first line of each test case description contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.
The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
The third line of the test case contains the binary string $$$s$$$ of length $$$n$$$.
The fourth line of the test case contains one integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.
The subsequent $$$q$$$ lines of the test case describe the queries. The first number of each query, $$$tp \in \{1, 2\}$$$, characterizes the type of the query: if $$$tp = 1$$$, then $$$2$$$ integers $$$1 \le l \le r \le n$$$ follow, meaning that the operation of type $$$1$$$ should be performed with parameters $$$l, r$$$, and if $$$tp = 2$$$, then one integer $$$g \in \{0, 1\}$$$ follows, meaning that the operation of type $$$2$$$ should be performed with parameter $$$g$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and also that the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, and for each query of type $$$2$$$ in it, output the answer to the corresponding query.
551 2 3 4 50100072 02 11 2 42 02 11 1 32 1612 12 14 14 5 500100132 11 2 42 147 7 7 777111132 01 2 32 021000000000 9961791791112 151 42 20 47 70001151 3 41 1 11 3 41 2 42 0
3 2 6 7 7 11 7 0 0 16430827 47
Let's analyze the first test case:
Name |
---|