PSUT ACM Round 1 (Div 1)
B. Card Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ cards stacked in a deck. Initially, $$$a_{i}$$$ is written on the $$$i$$$-th card from the top. The value written on a card does not change.

You will play a game. Initially your score is $$$0$$$. In each turn, you can do one of the following operations:

  • Choose an odd$$$^{\dagger}$$$ positive integer $$$i$$$, which is not greater than the number of cards left in the deck. Remove the $$$i$$$-th card from the top of the deck and add the number written on the card to your score. The remaining cards will be reindexed starting from the top.
  • Choose an even$$$^{\ddagger}$$$ positive integer $$$i$$$, which is not greater than the number of cards left in the deck. Remove the $$$i$$$-th card from the top of the deck. The remaining cards will be reindexed starting from the top.
  • End the game. You can end the game whenever you want, you do not have to remove all cards from the initial deck.

What is the maximum score you can get when the game ends?

$$$^{\dagger}$$$ An integer $$$i$$$ is odd, if there exists an integer $$$k$$$ such that $$$i = 2k + 1$$$.

$$$^{\ddagger}$$$ An integer $$$i$$$ is even, if there exists an integer $$$k$$$ such that $$$i = 2k$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). 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 second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output

For each test case, print a single integer — the maximum score you can get when the game ends.

Example
Input
4
4
-4 1 -3 5
4
1 -2 3 -4
3
-1 3 -5
1
-1
Output
5
4
2
0
Note

In the first test case, one can get the score of $$$5$$$ as follows:

  1. In the first turn, choose $$$i=2$$$. Your score remains $$$0$$$ and the numbers written on the cards from the top will become $$$[-4, -3, 5]$$$.
  2. In the second turn, choose $$$i=3$$$. Your score will become $$$5$$$ and the numbers written on the cards from the top will become $$$[-4, -3]$$$.
  3. In the third turn, end the game with the score of $$$5$$$.

In the second test case, one can get the score of $$$4$$$ as follows:

  1. In the first turn, choose $$$i=3$$$. Your score will become $$$3$$$ and the numbers written on the cards from the top will become $$$[1, -2, -4]$$$.
  2. In the second turn, choose $$$i=1$$$. Your score will become $$$4$$$ and the numbers written on the cards from the top will become $$$[-2, -4]$$$.
  3. In the third turn, end the game with the score of $$$4$$$.

In the third test case, one can get the score of $$$2$$$ as follows:

  1. In the first turn, choose $$$i=1$$$. Your score will become $$$-1$$$ and the numbers written on the cards from the top will become $$$[3, -5]$$$.
  2. In the second turn, choose $$$i=1$$$. Your score will become $$$2$$$ and the numbers written on the cards from the top will become $$$[-5]$$$.
  3. In the third turn, end the game with the score of $$$2$$$.

C. Cyclic Rotation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an array $$$a$$$ of length $$$n$$$. You may perform the following operation any number of times:

  • Choose two indices $$$l$$$ and $$$r$$$ where $$$1 \le l \lt r \le n$$$ and $$$a_l = a_r$$$. Then, set $$$a[l \ldots r] = [a_{l+1}, a_{l+2}, \ldots, a_r, a_l]$$$.

You are also given another array $$$b$$$ of length $$$n$$$ which is a permutation of $$$a$$$. Determine whether it is possible to transform array $$$a$$$ into an array $$$b$$$ using the above operation some number of times.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10 ^ 5$$$)  — the length of array $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)  — elements of the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$)  — elements of the array $$$b$$$.

It is guaranteed that $$$b$$$ is a permutation of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$

Output

For each test case, print "YES" (without quotes) if it is possible to transform array $$$a$$$ to $$$b$$$, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Example
Input
5
5
1 2 3 3 2
1 3 3 2 2
5
1 2 4 2 1
4 2 2 1 1
5
2 4 5 5 2
2 2 4 5 5
3
1 2 3
1 2 3
3
1 1 2
2 1 1
Output
YES
YES
NO
YES
NO
Note

In the first test case, we can choose $$$l=2$$$ and $$$r=5$$$ to form $$$[1, 3, 3, 2, 2]$$$.

In the second test case, we can choose $$$l=2$$$ and $$$r=4$$$ to form $$$[1, 4, 2, 2, 1]$$$. Then, we can choose $$$l=1$$$ and $$$r=5$$$ to form $$$[4, 2, 2, 1, 1]$$$.

In the third test case, it can be proven that it is not possible to transform array $$$a$$$ to $$$b$$$ using the operation.

D. A, B, AB and BA
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting of characters A and B.

Your task is to split it into blocks of length $$$1$$$ and $$$2$$$ in such a way that

  • there are no more than $$$a$$$ strings equal to "A";
  • there are no more than $$$b$$$ strings equal to "B";
  • there are no more than $$$ab$$$ strings "AB";
  • there are no more than $$$ba$$$ strings "BA";

Strings "AA" and "BB" are prohibited. Each character of the initial string $$$s$$$ should belong to exactly one block.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Next, $$$t$$$ independent cases follow.

The first line of each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 5 \cdot 10^5$$$) consisting only of characters A and/or B.

The second line of each test case contains four integers $$$a$$$, $$$b$$$, $$$ab$$$, and $$$ba$$$ ($$$0 \le a, b, ab, ba \le 5 \cdot 10^5$$$) — the maximum allowed number of strings "A", "B", "AB", and "BA" correspondingly.

It's guaranteed that the total length of $$$s$$$ doesn't exceed $$$5 \cdot 10^5$$$ over all test cases.

Output

For each test case, print YES if it's possible to split string $$$s$$$. Otherwise, print NO.

Example
Input
7
A
0 0 10 10
B
0 1 0 0
ABA
0 0 1 1
ABBABAAB
5 5 0 0
ABABBAABBAAB
1 1 2 3
ABBBBAB
0 3 2 0
BAABBA
1 3 2 0
Output
NO
YES
NO
YES
YES
YES
NO
Note

In the third test case, all possible splits are: A|B|A, AB|A or A|BA. All of them have at least one "A".

In the fourth test case, one of the possible splits is the following: A|B|B|A|B|A|A|B.

In the fifth test case, one of the possible splits is the following: A|BA|B|BA|AB|BA|AB.