Problems - Codeforces

IPL 2026

Yuuki is writing a problem and is coming up with the colors to use in the example.

Unfortunately, he wants to refer to each color with a one-character string corresponding to its first letter. This means he cannot use two colors that share the same first letter.

Given a list of $$$n$$$ color suggestions (one word, all uppercase letters), count the maximum number of colors he can use in the problem.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of color suggestions.

Each of the next $$$n$$$ lines contains a single string $$$s_i$$$ consisting of uppercase Latin letters ($$$1 \le |s_i| \le 20$$$) — a color suggestion.

Output

Print a single integer — the maximum number of colors Yuuki can use.

Examples

Input

5
RED
BLUE
GREEN
ROSE
BLACK

Output

Input

6
LIMEGREEN
LEMONYELLOW
LILAC
LIGHTBLUE
LICORICE
LAVENDAR

Output

Note

In the first testcase, Yuuki can choose the colors RED, GREEN, and BLACK which have first letters R G B respectively. It can be shown that Yuuki cannot choose more than three colors.

In the second testcase, Yuuki cannot choose more than one color, as any two colors share the same first letter.

You just finished an exam with $$$M$$$ questions where your score is the number of questions answered correctly. You know the scores of $$$n$$$ students in the class, your own, as well as some of your friends. The professor then announces the range of scores on the exam — the difference between the maximum score and the minimum score among all students in the class.

Since you have not been attending lectures, you do not know how many students are taking the class other than your friends. Determine the minimum total class size consistent with your information, or report that it is impossible.

Input

The first line contains three integers $$$n$$$, $$$M$$$, $$$D$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le M \le 10^9$$$, $$$0 \le D \le M$$$) — the number of students whose scores you know (including yourself), the number of questions, and the announced range.

The second line contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \le s_i \le M$$$) — the known scores.

Output

Print a single integer — the minimum total class size consistent with all given information. If no valid class exists, print impossible.

Examples

Input

2 100 75
10 70

Output

Input

2 100 50
10 90

Output

impossible

Input

3 100 80
10 50 90

Output

Ethan and Justin are arguing over how to sort a list of $$$n$$$ distinct integers. Ethan wants ascending order; Justin wants descending order. Unable to agree, they settle on a compromise: arrange the numbers in a zigzag pattern, so that the sequence alternately rises and falls.

A sequence $$$a_1, a_2, \ldots, a_n$$$ is zigzag if odd-indexed elements are local peaks (each is greater than its immediate neighbors) and even-indexed elements are local valleys (each is less than its immediate neighbors).

Given the list, output any re-ordering of the given integers so that the final sequence forms a zigzag sequence.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 200$$$) — the number of integers.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10000$$$) — the list.

Output

Print $$$n$$$ integers on a single line — any permutation of the input that forms a zigzag sequence. It is guaranteed that a solution always exists.

There are multiple possible correct answers — any correct answer will be accepted.

Examples

Input

5
1 2 3 4 5

Output

5 3 4 1 2

Input

4
2 7 1 8

Output

8 1 7 2

You are given an integer array $$$b$$$ of $$$n$$$ positive integers. For any non-negative integer $$$x$$$, define a new array $$$a$$$ by $$$a_i := b_i + x$$$ for every $$$1\le i\le n$$$.

An array $$$a$$$ is called separable if and only if there exists an index $$$i$$$ with $$$1\le i \lt n$$$ such that $$$$$$a_1+a_2+\cdots+a_i = a_{i+1}+a_{i+2}+\cdots+a_n.$$$$$$

For each test case, find the minimum non-negative integer $$$x$$$ such that the array obtained after adding $$$x$$$ to every element of $$$b$$$ is separable. If no such $$$x$$$ exists, output $$$-1$$$ instead.

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$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$-10^9\le b_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, output a single integer — the minimum non-negative integer $$$x$$$ such that the array $$$[b_1+x, b_2+x, \ldots, b_n+x]$$$ is separable. It can proven that under the constraints of this problem, if such integer exists, then it's never greater than $$$10^{18}$$$.

If no such integer exists, output $$$-1$$$.

Example

Input

Output

0
3
-1

Note

In the first test case, the array is already separable because $$$ 1+2=3. $$$ Therefore, the minimum valid value is $$$x=0$$$.

In the second test case, after adding $$$x=3$$$, the array becomes $$$ [4,5,6,7,8]. $$$ Now $$$ 4+5+6 = 7+8 = 15, $$$ so the array is separable. No smaller non-negative value works.

In the third test case, after adding any $$$x$$$, the array becomes $$$ [1+x,2+x]. $$$ The two parts would have sums $$$1+x$$$ and $$$2+x$$$, which can never be equal, so the answer is $$$-1$$$.

Alice and Bob are playing a game with a pile of $$$n$$$ stones.

They alternate turns removing stones from the pile, with Alice moving first. On her first turn, Alice must remove between $$$1$$$ and $$$k$$$ stones (inclusive).

On subsequent turns, if the previous player removed exactly $$$x$$$ stones, the next player must remove between $$$1$$$ and $$$x$$$ stones (inclusive).

The player who removes the last stone wins. Determine who wins if both players play optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1\le k\le n\le 10^{18}$$$) — the initial number of stones and the maximum number of stones Alice may remove on her first turn.

Output

For each test case, output the winner if both players play optimally.

Example

Input

6
6 1
6 2
12 3
12 4
67676767676768 1
67676767676769 67676767676768

Output

Bob
Alice
Bob
Alice
Bob
Alice

Auchenai is playing with his new letter game with a whole bunch of letter tiles available! More specifically, he has $$$a$$$ tiles of the letter $$$\tt{I}$$$, $$$b$$$ tiles of the letter $$$\tt{G}$$$, and $$$c$$$ tiles of the letter $$$\tt{M}$$$.

You are given positive integers $$$x$$$, $$$y$$$, and $$$z$$$. For any string $$$s$$$ that Auchenai constructs, he scores it as follows:

For every occurrence of the substring $$$\tt{IGM}$$$ in $$$s$$$, add $$$x$$$ points.
For every occurrence of the substring $$$\tt{GM}$$$ in $$$s$$$, add $$$y$$$ points.
For every occurrence of the substring $$$\tt{IM}$$$ in $$$s$$$, add $$$z$$$ points.

Note that substrings may overlap. For example, the string $$$\tt{IGMM}$$$ contains one occurrence of $$$\tt{IGM}$$$ and one occurrence of $$$\tt{GM}$$$ and thus would score $$$x+y$$$ points.

Auchenai wants to arrange all tiles into a single string of length $$$a + b + c$$$ so that its total score is maximized. Please help him achieve his goal!

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 next $$$t$$$ lines each contain six integers: $$$a, b, c, x, y, z$$$ ($$$0 \leq a, b, c \leq 2 \cdot 10^5$$$, $$$a+b+c \gt 0$$$, $$$1 \leq x, y, z \leq 10^9 $$$).

It is guaranteed that the sum of $$$a+b+c$$$ over all test cases does not exceed $$$6\cdot 10^5$$$.

Output

For each of the test cases, print two lines. In the first line, print the maximum possible score. In the second line, output any string consisting of $$$a$$$ $$$\tt{I}$$$'s, $$$b$$$ $$$\tt{G}$$$'s, and $$$c$$$ $$$\tt{M}$$$'s that achieves the maximum score.

Example

Input

8
1 1 1 5 3 2
3 1 3 10 4 7
2 2 2 100 5 6
3 3 3 10 1 2
5 4 0 100 100 100
4 0 3 100 7 5
2 2 2 3 4 5
4 3 4 1 3 10

Output

8
IGM
28
IGMIMIM
210
IGMIGM
33
IGMIGMIGM
0
IIIIIGGGG
15
IMIMIMI
14
IGMIGM
40
IMIMIMIMGGG

There exist two unknown sequences of positive integers $$$r_1,\ldots,r_n$$$ and $$$c_1,\ldots,c_m$$$. They define an $$$n\times m$$$ matrix $$$A$$$ by $$$$$$A_{ij} = \operatorname{lcm}(r_i, c_j)$$$$$$ for every $$$1\le i\le n$$$ and $$$1\le j\le m$$$.

Some entries of this matrix were lost. You are given an $$$n\times m$$$ table $$$b$$$. If $$$b_{ij}=0$$$, then the entry $$$A_{ij}$$$ is lost. Otherwise, it is known that $$$A_{ij}=b_{ij}$$$.

Among all pairs of sequences $$$(r_1,\ldots,r_n)$$$ and $$$(c_1,\ldots,c_m)$$$ consistent with all nonzero entries of $$$b$$$, minimize the product $$$$$$r_1 \times r_2\times \cdots\times r_n \times c_1 \times c_2\times \cdots \times c_m.$$$$$$

Since the answer may be very large, output it modulo $$$998244353$$$.

It is guaranteed that the given table is valid, i.e. at least one such pair of sequences always exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 500$$$) — the dimensions of the matrix.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains $$$m$$$ integers $$$b_{i1},b_{i2},\ldots,b_{im}$$$ ($$$0\le b_{ij}\le 10^8$$$). If $$$b_{ij}=0$$$, then the entry $$$A_{ij}$$$ is lost. Otherwise, it is known that $$$A_{ij}=b_{ij}$$$.

It is guaranteed that there exists at least one pair of positive-integer sequences $$$(r_1,\ldots,r_n)$$$ and $$$(c_1,\ldots,c_m)$$$ whose LCM matrix matches all nonzero entries of $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case, output a single integer — the minimum possible value of $$$$$$r_1 \times r_2\times \cdots\times r_n \times c_1 \times c_2\times \cdots \times c_m.$$$$$$taken modulo $$$998244353$$$.

Example

Input

Output

30
36
1

Auchenai is playing a long series of $$$n$$$ Riichi Mahjong games. After each game, he receives a positive performance feedback score from the MAKA AI and records his placement tier.

For the $$$i$$$-th game, let $$$a_i$$$ be MAKA's feedback score and $$$b_i\in \{1, 2\}$$$ be Auchenai's placement tier. A subsequence of games is called calm if the placement tiers are nondecreasing.

Given an integer $$$K$$$, Auchenai wants to know the maximum length $$$L$$$ of a calm subsequence whose average MAKA score is at least $$$K$$$. That is, the maximum $$$L$$$ such that there exists a sequence $$$1\le i_1\le i_2\le\ldots \le i_L\le n$$$ satisfying $$$b_{i_1} \leq b_{i_2}\le \ldots \leq b_{i_L}$$$ and $$$$$$\frac{a_{i_1} + a_{i_2}+\cdots + a_{i_L}}{L}\geq K.$$$$$$

If no such subsequence exists, output $$$0$$$.

Input

The first line contains two integers $$$n$$$ and $$$K$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq K \leq 10^9$$$) — the number of games and the desired average MAKA score.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the MAKA scores.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots , b_n$$$ ($$$b_i\in \{1, 2\}$$$) — the placement tiers.

Output

Output a single integer — the maximum length $$$L$$$ of a calm subsequence with average MAKA score at least $$$K$$$.

Examples

Input

5 4
5 4 6 4 3
1 1 2 2 2

Output

Input

8 6
9 2 8 7 1 2 10 6
1 2 1 2 1 1 2 2

Output

Input

8 8
3 9 3 9 3 9 3 9
1 2 1 2 1 2 1 2

Output

Alice and Bob are playing a game on $$$n$$$ piles of stones, numbered from $$$1$$$ to $$$n$$$. Initially, pile $$$i$$$ contains $$$a_i$$$ stones. Alice moves first.

On each move, the current player performs an operation once or twice. The operations are performed in succession, and each operation must be legal at the moment it is performed.

A single operation can be one of the following:

choose an index $$$i$$$ such that pile $$$i$$$ is non-empty, then remove one stone from pile $$$i$$$;
choose indices $$$i \lt j$$$ such that pile $$$i$$$ is non-empty, then remove one stone from pile $$$i$$$ and add one stone to pile $$$j$$$.

A player who cannot make a move loses.

Determine who wins if both players play optimally. If Alice wins, output any winning first move for her.

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 number of piles.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^{18}$$$) — the initial sizes of the piles.

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

Output

For each test case:

if Bob wins, output a single line containing Bob;
otherwise, output a line containing Alice and an integer $$$q$$$ ($$$1\le q\le 2$$$) — the number of operations in Alice's first move. Then output $$$q$$$ more lines describing these operations in the order they are performed.

Each operation must have one of the following forms:

1 i — remove one stone from pile $$$i$$$;
2 i j — remove one stone from pile $$$i$$$ and add one stone to pile $$$j$$$.

All printed operations must be legal when they are performed.

If there are multiple valid answers, output any of them.

Example

Input

5
2
1 2
2
3 3
3
1 1 2
3
1 1 1
2
100000007998244353 6769676967696769

Output

Alice 1
2 1 2
Bob
Alice 2
2 1 3
1 2
Alice 2
2 1 3
2 2 3
Alice 2
1 1
1 2

You are given two tournaments $$$A$$$ and $$$B$$$ on the same set of vertices $$$1,2,\ldots,n$$$. Recall that a tournament is an orientation of the complete graph: for every pair of distinct vertices $$$i$$$ and $$$j$$$, exactly one of the edges $$$i\to j$$$ or $$$j\to i$$$ exist.

You may perform the following operation on the tournament $$$A$$$ any number of times:

Choose three distinct vertices $$$x$$$, $$$y$$$, and $$$z$$$ such that there exists a cycle $$$x\to y\to z\to x$$$ in the current tournament $$$A$$$;
Reverse all three edges among these vertices. That is, orient the edges to make the cycle $$$x\leftarrow y\leftarrow z\leftarrow x$$$

Find any sequence of operations that transforms $$$A$$$ into $$$B$$$, or determine that it is impossible.

It can be shown that whenever it is possible, there exists a valid sequence using at most $$$\frac{n(n-1)}{2}$$$ operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line contains a single integer $$$t$$$ — the number of test cases.

Each test case begins with a single integer $$$n$$$ ($$$2 \le n \le 500$$$) — the number of vertices.

The next $$$n$$$ lines describe tournament $$$A$$$. The $$$i$$$-th of these lines contains a binary string $$$A_i$$$ of length $$$n$$$. Here, $$$A_{ij}=1$$$ means that vertex $$$i$$$ beats vertex $$$j$$$ in tournament $$$A$$$, and $$$A_{ij}=0$$$ means otherwise.

The next $$$n$$$ lines describe tournament $$$B$$$ in the same format.

It is guaranteed that both $$$A$$$ and $$$B$$$ are valid tournaments, i.e.:

$$$A_{ii}=B_{ii}=0$$$ for every $$$i$$$;
for every $$$i \ne j$$$, exactly one of $$$A_{ij}$$$ and $$$A_{ji}$$$ equals $$$1$$$;
for every $$$i \ne j$$$, exactly one of $$$B_{ij}$$$ and $$$B_{ji}$$$ equals $$$1$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case:

if it is impossible to transform $$$A$$$ into $$$B$$$, output a single line containing $$$-1$$$;
otherwise, output a single integer $$$k$$$ ($$$0 \le k \le \frac{n(n-1)}{2}$$$) — the number of operations. Then output $$$k$$$ lines. The $$$i$$$-th of them must contain three distinct integers $$$x$$$, $$$y$$$, and $$$z$$$ such that, immediately before this operation, the current tournament contains the directed cycle $$$x \to y \to z \to x$$$.

If there are multiple valid answers, output any of them.

Example

Input

Output

1
2 3 1
-1

This is an interactive problem.

There is a hidden binary string $$$s$$$ of length $$$n$$$. It is guaranteed that $$$s$$$ contains at least one character 1, and you wish to find a 1.

In each query, you may ask if a substring $$$s_ls_{l+1} \ldots s_r$$$ contains a 1. However, there is an additional restriction:

If your previous query had length $$$L$$$, then every future query must have length at least $$$L$$$. In other words, the sequence of query lengths must be nondecreasing.

Find the index of any character 1 using at most $$$100$$$ queries.

The length of a query $$$\texttt{?}\;l\; r$$$ is defined as $$$r - l + 1$$$.

Input

At the beginning of the interaction, you are given a single integer $$$n$$$ ($$$1\le n\le 10^4$$$) — the length of the hidden string.

It is guaranteed that the hidden string contains no characters other than 0s and 1s, and that it contains at least one 1.

Interaction

To make a query, print a line in the following format:

$$$\texttt{?}\;l\;r$$$ ($$$1\le l\le r\le n$$$) — the indices chosen for the query.

After you print a query, the interactor will respond with a single integer:

1 if the substring $$$s_l s_{l+1}\ldots s_r$$$ contains at least one 1;
0 otherwise.

When you are ready to give the final answer, print a line of the form

! $$$p$$$, where $$$1\le p\le n$$$ and $$$s_p=\texttt{1}$$$,

and flush the output.

If you make an invalid query, ask more than $$$100$$$ queries, or break the nondecreasing-length rule, the interactor may reply with -1. In that case, your program must terminate immediately.

Note that the final answer does not count as a query.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

The interactor is not adaptive; the hidden string is fixed before the interaction starts.

$$$^{\text{∗}}$$$To flush, use:

fflush(stdout) or cout.flush() in C++;
sys.stdout.flush() in Python;
see the documentation for other languages.

Example

Input

Output

Note

The hidden string in this test is 00100001.

Note that the lengths of the three queries are $$$1$$$, $$$3$$$, and $$$3$$$ in order. Because $$$s_8 = \texttt{1}$$$, the answer to the query $$$\texttt{?}\;6\;8$$$ is $$$1$$$.

Find a set $$$T$$$ of $$$n$$$ distinct positive integers such that:

All integers in $$$T$$$ are at most $$$10^5$$$.
There does not exist a non-empty subset $$$S$$$ of $$$T$$$ with size less than or equal to $$$8$$$ such that the sum of elements in $$$S$$$ is a perfect square.

Input

A single integer $$$n$$$ ($$$1 \le n \le 2862$$$) — the size of the set you must produce.

Output

On a single line, print $$$n$$$ distinct integers, each between $$$1$$$ and $$$10^5$$$ inclusive, satisfying the conditions above. Any valid answer will be accepted.

Example

Input

Output

26 70 84 90 92

Franklin loves cactus graphs and wants you to construct a special cactus for him. In particular, he wants you to construct a tree (a cactus with no cycles) satisfying the following constraint.

For a fixed tree, define $$$f(k)$$$ to be the number of unordered pairs of vertices whose distance between them is exactly $$$k$$$. Franklin gives you three integers $$$x$$$, $$$y$$$, and $$$z$$$. Construct any tree satisfying $$$$$$ f(x)=f(y)=f(z) \gt 0. $$$$$$

If there are multiple valid trees, output any of them.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20$$$). The description of the test cases follows.

The only line of each test case contains three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1\le x \lt y \lt z\le 100$$$).

Output

For each test case, first output a single integer $$$n$$$ ($$$1\le n\le 10^4$$$) — the number of vertices in your tree.

Then output $$$n-1$$$ lines describing the edges of the tree. Each line should contain two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$), meaning that there is an edge between vertices $$$u$$$ and $$$v$$$.

The printed graph must be a tree, and it must satisfy $$$f(x)=f(y)=f(z) \gt 0$$$.

If there are multiple valid answers, output any of them.

Example

Input

2
1 3 5
1 3 5

Output

Note

The two sample tests are identical. The sample output is shown below.

$\text{[math]}$

Here, $$$f(1) = f(3) = f(5) = 11$$$. For example, the distance between nodes $$$6$$$ and $$$7$$$ is $$$1$$$, and the distance between nodes $$$8$$$ and $$$9$$$ is $$$5$$$.

The land of Transportopia consists of $$$n$$$ cities, numbered from $$$1$$$ to $$$n$$$, each located equally spaced on a line. Each city has a single airport, run by a single company.

You are given a string $$$s$$$ of length $$$n$$$, consisting of uppercase Latin letters, where the $$$i$$$-th character denotes which company owns the airport in city $$$i$$$.

In your visit to Transportopia, you are trying to travel from city $$$1$$$ to city $$$n$$$ as quickly as possible. You can take a $$$1$$$ hour bus ride between any two adjacent cities or a $$$1$$$ hour flight between any two cities $$$i$$$ and $$$j$$$, as long as their airports are owned by the same company (i.e. $$$s_i = s_j$$$).

Unfortunately, you can only afford to buy at most one plane ticket. Under these conditions, what is the minimum number of hours it takes to travel from city $$$1$$$ to city $$$n$$$?

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of cities.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of uppercase Latin letters — the company that owns each city's airport.

Output

Print a single integer — the minimum number of hours it takes to travel from city $$$1$$$ to city $$$n$$$.

Examples

Input

7
ABCDACB

Output

Input

5
AAAAA

Output

Input

5
YUUKI

Output

Input

5
ETHAN

Output

Auchenai graduated from UIUC last semester and started to work!

Unfortunately, he wants to do some grocery shopping but has only limited time. There are $$$n$$$ shops that Auchenai wants to visit, and shopping at shop $$$i$$$ takes exactly $$$t_i$$$ units of time. What is even worse, there are $$$m$$$ other people — the $$$j$$$-th person will join the queue of shop $$$s_j$$$ at time $$$u_j$$$.

At time $$$0$$$, Auchenai may choose any one shop to visit first. After finishing shopping at one shop, he may immediately go to any other unvisited shop. Moving between shops takes no time.

Each shop has exactly one queue and serves people one by one in arrival order. If Auchenai arrives at a shop while someone is being served or waiting in line, he must wait until all people before him finish. If several people arrive at the same time, all other people are considered to join before Auchenai. Every person shopping at shop $$$i$$$, including Auchenai, occupies the shop for exactly $$$t_i$$$ units of time.

Help Auchenai find the earliest possible time that he can finish shopping (i.e., the moment he finishes shopping at the last shop).

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 18$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$t_1, t_2, \ldots ,t_n$$$ ($$$ 1 \leq t_i \leq 10^9$$$), where $$$t_i$$$ is the time needed to shop at shop $$$i$$$.

Each of the next $$$m$$$ lines contains two integers $$$s_j$$$ and $$$u_j$$$, ($$$1 \leq s_j \leq n$$$, $$$1 \leq u_j \leq 10^9$$$), meaning that the $$$j$$$-th person joins the queue of shop $$$s_j$$$ at time $$$u_j$$$.

Output

Output a single integer — the earliest possible time that Auchenai can finish shopping.

Examples

Input

Output

Input

Output

Input

Output

Input

Output

You are given a binary string $$$s$$$ of length $$$2n-1$$$.

For each test case, output a binary string $$$t$$$ of length $$$n$$$ such that $$$t$$$ is not a subsequence of $$$s$$$.

Recall that a string $$$a$$$ is a subsequence of a string $$$b$$$ if and only if $$$a$$$ can be obtained from $$$b$$$ by deleting zero or more characters without changing the order of the remaining characters.

It can be proven that under the given constraints, at least one valid answer always exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2\cdot 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 a binary string $$$s$$$ of length $$$2n-1$$$.

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

Output

For each test case, output a binary string $$$t$$$ of length $$$n$$$ such that $$$t$$$ is not a subsequence of $$$s$$$.

If there are multiple valid answers, print any of them.

Each answer may be printed on its own line.

Example

Input

Output