vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a string of words, you need to find the highest scoring word.

Each letter of a word scores points according to its position in the alphabet: `a = 1, b = 2, c = 3` etc.

You need to return the highest scoring word as a string.

If two words score the same, return the word that appears earliest in the original string.

All letters will be lowercase and all inputs will be valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I found this interesting interview question just today:

> *8 coins are given where all the coins have equal weight, except one. The odd one weights less than the others, not being of pure gold. In the worst case, how many iterations are actually needed to find the odd one out on a two plates scale*.

I am asking you then to tell me what is the *minimum* amount of weighings it will take to measure `n` coins in every possible occurrence (including worst case scenario, ie: without relying on luck at all).

`n` is guaranteed to be a positive integer.

***Tip:*** being able to think *recursively* might help here :p

***Note:*** albeit this is more clearly a logical than a coding problem, do not underestimate (or under-rank) the kata for requiring not necessarily wizard-class coding skills: a good coder is a master of pattern recognition and subsequent optimization ;)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two strings s and t, consisting only of letters a and b. You can make the following operation several times: choose a prefix of s, a prefix of t and swap them. Prefixes can be empty, also a prefix can coincide with a whole string. 

Your task is to find a sequence of operations after which one of the strings consists only of a letters and the other consists only of b letters. The number of operations should be minimized.

Input

The first line contains a string s (1 ≤ |s| ≤ 2·105).

The second line contains a string t (1 ≤ |t| ≤ 2·105).

Here |s| and |t| denote the lengths of s and t, respectively. It is guaranteed that at least one of the strings contains at least one a letter and at least one of the strings contains at least one b letter.

Output

The first line should contain a single integer n (0 ≤ n ≤ 5·105) — the number of operations.

Each of the next n lines should contain two space-separated integers ai, bi — the lengths of prefixes of s and t to swap, respectively.

If there are multiple possible solutions, you can print any of them. It's guaranteed that a solution with given constraints exists.

Examples

Input

bab
bb


Output

2
1 0
1 3


Input

bbbb
aaa


Output

0

Note

In the first example, you can solve the problem in two operations:

  1. Swap the prefix of the first string with length 1 and the prefix of the second string with length 0. After this swap, you'll have strings ab and bbb. 
  2. Swap the prefix of the first string with length 1 and the prefix of the second string with length 3. After this swap, you'll have strings bbbb and a. 



In the second example, the strings are already appropriate, so no operations are needed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a road consisting of several rows. Each row is divided into several rectangular tiles, and all tiles in the same row are equal. The first row contains exactly one rectangular tile. Look at the picture below which shows how the tiles are arranged.

The road is constructed as follows: 

  * the first row consists of 1 tile; 
  * then a_1 rows follow; each of these rows contains 1 tile greater than the previous row; 
  * then b_1 rows follow; each of these rows contains 1 tile less than the previous row; 
  * then a_2 rows follow; each of these rows contains 1 tile greater than the previous row; 
  * then b_2 rows follow; each of these rows contains 1 tile less than the previous row; 
  * ... 
  * then a_n rows follow; each of these rows contains 1 tile greater than the previous row; 
  * then b_n rows follow; each of these rows contains 1 tile less than the previous row. 

<image> An example of the road with n = 2, a_1 = 4, b_1 = 2, a_2 = 2, b_2 = 3. Rows are arranged from left to right. 

You start from the only tile in the first row and want to reach the last row (any tile of it). From your current tile, you can move to any tile in the next row which touches your current tile.

Calculate the number of different paths from the first row to the last row. Since it can be large, print it modulo 998244353.

Input

The first line contains one integer n (1 ≤ n ≤ 1000).

Then n lines follow. The i-th of them contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ 10^5; |a_i - b_i| ≤ 5).

Additional constraint on the input: the sequence of a_i and b_i never results in a row with non-positive number of tiles.

Output

Print one integer — the number of paths from the first row to the last row, taken modulo 998244353.

Examples

Input


2
4 2
2 3


Output


850


Input


3
4 1
2 3
3 1


Output


10150


Input


8
328 323
867 868
715 718
721 722
439 435
868 870
834 834
797 796


Output


759099319

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During the "Russian Code Cup" programming competition, the testing system stores all sent solutions for each participant. We know that many participants use random numbers in their programs and are often sent several solutions with the same source code to check.

Each participant is identified by some unique positive integer k, and each sent solution A is characterized by two numbers: x — the number of different solutions that are sent before the first solution identical to A, and k — the number of the participant, who is the author of the solution. Consequently, all identical solutions have the same x.

It is known that the data in the testing system are stored in the chronological order, that is, if the testing system has a solution with number x (x > 0) of the participant with number k, then the testing system has a solution with number x - 1 of the same participant stored somewhere before.

During the competition the checking system crashed, but then the data of the submissions of all participants have been restored. Now the jury wants to verify that the recovered data is in chronological order. Help the jury to do so.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 10^5) — the number of solutions. Each of the following n lines contains two integers separated by space x and k (0 ≤ x ≤ 10^5; 1 ≤ k ≤ 10^5) — the number of previous unique solutions and the identifier of the participant.


-----Output-----

A single line of the output should contain «YES» if the data is in chronological order, and «NO» otherwise.


-----Examples-----
Input
2
0 1
1 1

Output
YES

Input
4
0 1
1 2
1 1
0 2

Output
NO

Input
4
0 1
1 1
0 1
0 2

Output
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The time on the planet Lapituletti goes the same way it goes on Earth but a day lasts $h$ hours and each hour lasts $m$ minutes. The inhabitants of that planet use digital clocks similar to earth ones. Clocks display time in a format HH:MM (the number of hours in decimal is displayed first, then (after the colon) follows the number of minutes in decimal; the number of minutes and hours is written with leading zeros if needed to form a two-digit number). Hours are numbered from $0$ to $h-1$ and minutes are numbered from $0$ to $m-1$.

That's how the digits are displayed on the clock. Please note that digit $1$ is placed in the middle of its position.

A standard mirror is in use on the planet Lapituletti. Inhabitants often look at the reflection of the digital clocks in the mirror and feel happy when what you see on the reflected clocks is a valid time (that means that you see valid digits in the reflection and this time can be seen on the normal clocks at some moment of a day).

The image of the clocks in the mirror is reflected against a vertical axis.

The reflection is not a valid time.

The reflection is a valid time with $h=24$, $m = 60$. However, for example, if $h=10$, $m=60$, then the reflection is not a valid time.

An inhabitant of the planet Lapituletti begins to look at a mirrored image of the clocks at some time moment $s$ and wants to know the nearest future time moment (which can possibly happen on the next day), when the reflected clock time is valid.

It can be shown that with any $h$, $m$, $s$ such a moment exists. If the reflected time is correct at the moment the inhabitant began to look at the clock, that moment is considered the nearest.

You are asked to solve the problem for several test cases.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$) — the number of test cases.

The next $2 \cdot T$ lines contain the description of test cases. The description of each test case consists of two lines.

The first line of a test case contains two integers $h$, $m$ ($1 \le h, m \le 100$).

The second line contains the start time $s$ in the described format HH:MM.


-----Output-----

For each test case output in a separate line the nearest moment in format HH:MM when the reflected time is correct.


-----Examples-----

Input
5
24 60
12:21
24 60
23:59
90 80
52:26
1 100
00:01
10 10
04:04
Output
12:21
00:00
52:28
00:00
00:00


-----Note-----

In the second test case it is not hard to show that the reflection of 23:59 is incorrect, while the reflection of the moment 00:00 on the next day is correct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i, and the color and length of that edge are c_i and d_i, respectively. Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

* Query j (1 \leq j \leq Q): assuming that the length of every edge whose color is x_j is changed to y_j, find the distance between Vertex u_j and Vertex v_j. (The changes of the lengths of edges do not affect the subsequent queries.)

Constraints

* 2 \leq N \leq 10^5
* 1 \leq Q \leq 10^5
* 1 \leq a_i, b_i \leq N
* 1 \leq c_i \leq N-1
* 1 \leq d_i \leq 10^4
* 1 \leq x_j \leq N-1
* 1 \leq y_j \leq 10^4
* 1 \leq u_j < v_j \leq N
* The given graph is a tree.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
a_1 b_1 c_1 d_1
:
a_{N-1} b_{N-1} c_{N-1} d_{N-1}
x_1 y_1 u_1 v_1
:
x_Q y_Q u_Q v_Q


Output

Print Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to Query j.

Example

Input

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4


Output

130
200
60

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Tom Riddle's Diary

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Harry Potter is on a mission to destroy You-Know-Who's Horcruxes. The first Horcrux that he encountered in the Chamber of Secrets is Tom Riddle's diary. The diary was with Ginny and it forced her to open the Chamber of Secrets. Harry wants to know the different people who had ever possessed the diary to make sure they are not under its influence.

He has names of *n* people who possessed the diary in order. You need to tell, for each person, if he/she possessed the diary at some point before or not.

Formally, for a name *s**i* in the *i*-th line, output "YES" (without quotes) if there exists an index *j* such that *s**i*<==<=*s**j* and *j*<=&lt;<=*i*, otherwise, output "NO" (without quotes).

Input Specification:
First line of input contains an integer *n* (1<=≤<=*n*<=≤<=100) — the number of names in the list.

Next *n* lines each contain a string *s**i*, consisting of lowercase English letters. The length of each string is between 1 and 100.

Output Specification:
Output *n* lines each containing either "YES" or "NO" (without quotes), depending on whether this string was already present in the stream or not.

You can print each letter in any case (upper or lower).

Demo Input:
['6\ntom\nlucius\nginny\nharry\nginny\nharry\n', '3\na\na\na\n']

Demo Output:
['NO\nNO\nNO\nNO\nYES\nYES\n', 'NO\nYES\nYES\n']

Note:
In test case 1, for *i* = 5 there exists *j* = 3 such that *s*<sub class="lower-index">*i*</sub> = *s*<sub class="lower-index">*j*</sub> and *j* &lt; *i*, which means that answer for *i* = 5 is "YES".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation of length n is a sequence of integers from 1 to n of length n containing each number exactly once. For example, [1], [4, 3, 5, 1, 2], [3, 2, 1] are permutations, and [1, 1], [0, 1], [2, 2, 1, 4] are not.

There was a permutation p[1 ... n]. It was merged with itself. In other words, let's take two instances of p and insert elements of the second p into the first maintaining relative order of elements. The result is a sequence of the length 2n.

For example, if p=[3, 1, 2] some possible results are: [3, 1, 2, 3, 1, 2], [3, 3, 1, 1, 2, 2], [3, 1, 3, 1, 2, 2]. The following sequences are not possible results of a merging: [1, 3, 2, 1, 2, 3], [3, 1, 2, 3, 2, 1], [3, 3, 1, 2, 2, 1].

For example, if p=[2, 1] the possible results are: [2, 2, 1, 1], [2, 1, 2, 1]. The following sequences are not possible results of a merging: [1, 1, 2, 2], [2, 1, 1, 2], [1, 2, 2, 1].

Your task is to restore the permutation p by the given resulting sequence a. It is guaranteed that the answer exists and is unique.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 400) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 50) — the length of permutation. The second line of the test case contains 2n integers a_1, a_2, ..., a_{2n} (1 ≤ a_i ≤ n), where a_i is the i-th element of a. It is guaranteed that the array a represents the result of merging of some permutation p with the same permutation p.

Output

For each test case, print the answer: n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n), representing the initial permutation. It is guaranteed that the answer exists and is unique.

Example

Input


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


Output


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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bosky is a very curious child who turned 13 yesterday. His parents gifted him a digital watch which he really liked. He was amazed to see how each number can be represented inside one cell only by switching different edges on and off.

Today, while he was in his home alone, getting bored looking at his watch, an idea popped up in his scientific mind. He immediately went to the garage and picked up a long rectangular cardboard, which was 2 units wide and L units long, and lots of thin LED tubes which were 1 unit long.

Bosky wanted to place LED tubes on the rectangular cardboard in such a way that he can represent as many digits as possible using the LED tubes and rectangular board similar to how digits are represented on his watch.

He realized that none of the LED tubes are working so he decided to purchase new LED tubes.

Each LED tube will cost Rs. 7

He has Rs. M with him and he now goes to market and spends all the money purchasing LED tubes.

After he brought all the LED tubes home, he wondered how many different digits he can represent on the rectangular board such that he doesn't have to repeat a number again.

But Bosky is tired now and does not want to try all the possible combinations to figure out how many digits he can represent on the board. He knows that you are a great programmer and you would surely help him. He calls you and tells you the length L and the amount of money M he has. Now, you have to tell him how many different digits he can represent on the rectangular board such that none of the digits is repeated, given:

0 requires -- 6 tubes

1 requires -- 2 tubes

2 requires -- 5 tubes

3 requires -- 5 tubes

4 requires -- 4 tubes

5 requires -- 5 tubes

6 requires -- 6 tubes

7 requires -- 3 tubes

8 requires -- 7 tubes

9 requires -- 6 tubes

[NOTE: Each digit occupies exactly 1 unit length on the board]

Input:

Input will contain a number T denoting the number of test cases. 

Then T test cases follow, each one consisting of two space-separated integers L and M .

Output

For each test case, output a single integer - the number of different digits Bosky can represent on the rectangular board such that none of the number is repeated and all the digits fit on the board.

Constraints

1  ≤ T  ≤ 100

0 ≤ M ≤ 2000

0 ≤ L ≤ 10

SAMPLE INPUT
4
1 14
1 50
4 28
5 700

SAMPLE OUTPUT
1
10
3
32491

Explanation

Case 1: He has 14 rupees and he can purchase 2 LED tubes using which he can represent only '1' on the board.

Case 2: He can purchase 7 LED tubes using 50 rupees and the number of digits he can represent using 7 tubes are 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has a multiset s consisting of n integer numbers. Vasya calls some number x nice if it appears in the multiset exactly once. For example, multiset \{1, 1, 2, 3, 3, 3, 4\} contains nice numbers 2 and 4.

Vasya wants to split multiset s into two multisets a and b (one of which may be empty) in such a way that the quantity of nice numbers in multiset a would be the same as the quantity of nice numbers in multiset b (the quantity of numbers to appear exactly once in multiset a and the quantity of numbers to appear exactly once in multiset b).

Input

The first line contains a single integer n~(2 ≤ n ≤ 100).

The second line contains n integers s_1, s_2, ... s_n~(1 ≤ s_i ≤ 100) — the multiset s.

Output

If there exists no split of s to satisfy the given requirements, then print "NO" in the first line.

Otherwise print "YES" in the first line.

The second line should contain a string, consisting of n characters. i-th character should be equal to 'A' if the i-th element of multiset s goes to multiset a and 'B' if if the i-th element of multiset s goes to multiset b. Elements are numbered from 1 to n in the order they are given in the input.

If there exist multiple solutions, then print any of them.

Examples

Input

4
3 5 7 1


Output

YES
BABA


Input

3
3 5 1


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef Watson uses a social network called ChefBook, which has a new feed consisting of posts by his friends. Each post can be characterized by f - the identifier of the friend who created the post, p - the popularity of the post(which is pre-calculated by ChefBook platform using some machine learning algorithm) and s - the contents of the post which is a string of lower and uppercase English alphabets.
Also, Chef has some friends, which he has marked as special.

The algorithm used by ChefBook for determining the order of posts in news feed is as follows:
Posts of special friends should be shown first, irrespective of popularity. Among all such posts the popular ones should be shown earlier.
Among all other posts, popular posts should be shown earlier.
Given, a list of identifiers of Chef's special friends and a list of posts, you have to implement this algorithm for engineers of ChefBook and output the correct ordering of posts in the new feed. 

------ Input ------ 

First line contains N, number of special friends of Chef and M, the number of posts. Next line contains N integers A_{1}, A_{2}, ..., A_{N} denoting the identifiers of special friends of Chef. Each of the next M lines contains a pair of integers and a string denoting f, p and s, identifier of the friend who created the post, the popularity of the post and the contents of the post, respectively. It is guaranteed that no two posts have same popularity, but the same friend might make multiple posts.

------ Output ------ 

Output correct ordering of posts in news feed in M lines. Output only the contents of a post.

------ Constraints ------ 

$1 ≤ N, M ≤ 10^{3}$
$1 ≤ A_{i}, f, p ≤  10^{5}$
$1 ≤ length(s) ≤  100$

----- Sample Input 1 ------ 
2 4

1 2

1 1 WhoDoesntLoveChefBook

2 2 WinterIsComing

3 10 TheseViolentDelightsHaveViolentEnds

4 3 ComeAtTheKingBestNotMiss
----- Sample Output 1 ------ 
WinterIsComing

WhoDoesntLoveChefBook

TheseViolentDelightsHaveViolentEnds

ComeAtTheKingBestNotMiss
----- explanation 1 ------ 
Friends $1$ and $2$ are special. Among them, friend $2$'s post has more popularity. Thus, the first two posts of the feed would be of friend $2$ and $1$ respectively.  
From remaining friends, i.e., friends $3$ and $4$, friend $4$'s post has more popularity. Thus, it would be shown earlier in the feed.  
The final ordering of posts is $2\rightarrow 1\rightarrow 4\rightarrow 3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Its Diwali time and there are LED series lights everywhere. Little Roy got curious about how LED lights work.

He noticed that in one single LED Bulb there are 3 LED lights, namely Red, Green and Blue.

State of the bulb at any moment is the sum of Red, Green and Blue LED light.

Bulb works as follows:

Roy took out all the LEDs and found that Red LED stays ON for R seconds, Green LED stays ON for G seconds and Blue LED stays ON for B seconds. Similarly they stay OFF for same respective R, G, B number of seconds. (Initially all the LEDs are OFF. See Sample Test Case Explanation for better understanding)

Roy has one query for you, given the total number of seconds T, find the number of seconds Red, Green, Blue, Yellow, Cyan, Magenta, White, Black(no light) lights are visible.

Input:

One line containing space separated integers T, R, G, B

Output:

One line containing 8 space separated integers indicating the number of seconds Red, Green, Blue, Yellow, Cyan, Magenta, White, Black (no light) lights are visible. (See Sample I/O for clarification)

Constraints:

 1 ≤ T, R, G, B ≤ 1000000 

Sample Test Case Explanation:SAMPLE INPUT
12 2 3 5

SAMPLE OUTPUT
1 1 1 3 2 2 0 2

Explanation

As shown in the image above, we have 0 to 11, a total of 12 seconds. State of Bulb for each second is also shown. Red, Blue and Green occur for 1 second; Yellow occur for 3 seconds; Cyan, Magenta and Black occur for 2 seconds and White does not occur at all. (Remember you have to output in R, G, B, Y, C, M, W, B sequence and hence the output is (1\; 1\; 1\; 3\; 2\; 2\; 0\; 2)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.