Codeforces Round 953 (Div. 2) |
---|
Finished |
Sasha has two binary strings $$$s$$$ and $$$t$$$ of the same length $$$n$$$, consisting of the characters 0 and 1.
There is also a computing machine that can perform two types of operations on binary strings $$$a$$$ and $$$b$$$ of the same length $$$k$$$:
Sasha became interested in the following: if we consider the string $$$a=s_ls_{l+1}\ldots s_r$$$ and the string $$$b=t_lt_{l+1}\ldots t_r$$$, what is the maximum number of 1 characters in the string $$$a$$$ that can be obtained using the computing machine. Since Sasha is very curious but lazy, it is up to you to answer this question for several pairs $$$(l_i, r_i)$$$ that interest him.
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the strings $$$s$$$ and $$$t$$$.
The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$, consisting of the characters 0 and 1.
The third line of each test case contains a binary string $$$t$$$ of length $$$n$$$, consisting of the characters 0 and 1.
The fourth line of each test case contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.
The $$$i$$$-th of the following lines contains two integers $$$l_{i}$$$ and $$$r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le n$$$) — the boundaries of the $$$i$$$-th pair of substrings that interest Sasha.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$q$$$ integers — the answers to all queries.
341111000021 22 441010110121 31 4601010101101052 31 62 54 43 6
2 3 2 3 1 4 3 1 2
In the first test case:
In the second test case:
Name |
---|