vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are n players sitting at a round table. All of them have s cards of n colors in total. Besides, initially the first person had cards of only the first color, the second one had cards of only the second color and so on. They can swap the cards by the following rules: 

  * as the players swap, a player can give a card of his color only; 
  * a player can't accept a card of a color he already has (particularly, he can't take cards of his color, no matter whether he has given out all of them or not); 
  * during one swap a pair of people swaps cards (each person gives one card and takes one card). 



The aim of all n people is as follows: each of them should give out all the cards he had initially (that is, all cards of his color). Your task is to denote whether such sequence of swaps is possible. If the answer is positive, you should list all the swaps.

Input

The first line contains integers n (1 ≤ n ≤ 200000) and s (1 ≤ s ≤ 200000). The second line contains n numbers, the i-th number stands for how many cards the i-th player has by the moment the game starts. It is possible that a player has no cards initially.

Output

On the first line print "No" if such sequence of swaps is impossible. Otherwise, print "Yes". If the answer is positive, next print number k — the number of the swaps. Then on k lines describe the swaps by pairs of indices of the swapping players. Print the swaps and the numbers of the swaps in any order.

Examples

Input

4 8
2 2 2 2


Output

Yes
4
4 3
4 2
1 3
1 2


Input

6 12
1 1 2 2 3 3


Output

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


Input

5 5
0 0 0 0 5


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xsquare is not good at Mathematics, but his Mathematics teacher considers him the most brilliant student of the class. How come ? Actually Xsquare was the only one to complete the Mathematics Assignment given by his maths teacher by solving a very hard problem.

Lets first describe the problem given in the Xsquare's Assignment .

Given an integer X where (X ≤ 10^10) . Count the number of ways of representing integer X as sum of two Squares? Easy one , Isn't it ?

Xsquare tried hard and finally solved this problem. 

Now, his Mathematics teacher thinks that Xsquare can solve the same problem with higher constaints, say for X=10^1000. On the Other hand his mathematics teacher also knows that Xsquare is frightened of very big numbers. So, he decided to represent the number X as the product of N numbers. 

Xsquare knows that he cannot solve this problem with huge constraints. But on the same side, he does not want to disappoint his Mathematics teacher. So, he asked you for help. 

Your task is very very simple : Given N  numbers, you need to tell the number of ways of representing the product of these N numbers as sum of two squares.

Look at the sample test case for better understanding of the problem.

INPUT:

First line of input contains a single integer N denoting the number of numbers. Next line of input contains N space separated integers denoting the values of N numbers.

OUTPUT:

Output the number of ways of representing the given number X as sum of two squares, Where X = Product of given N numbers.

NOTE

Number of ways of representing a number X as sum of two squares can be very large. so output the answer mod 10^9+7.

CONSTRAINTS:

1 ≤ N ≤ 200

1 ≤ X ≤ 10^2000

None of the N numbers exceeds 10^10.

SAMPLE INPUT
3
2 1 2

SAMPLE OUTPUT
4

Explanation

Explanation:

212=4

There are 4 ways of representing 4 as sum of two squares.

0^2 + 2^2 = 4
0^2 + (-2)^2 = 4
2^2 + 0^2 = 4 
(-2)^2 + 0^2 = 4

Look at the explanation of the sample test case and notice that the sign as well as order matters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given an array a_1, …, a_n of n non-negative integers.

Let's call it sharpened if and only if there exists an integer 1 ≤ k ≤ n such that a_1 < a_2 < … < a_k and a_k > a_{k+1} > … > a_n. In particular, any strictly increasing or strictly decreasing array is sharpened. For example:

  * The arrays [4], [0, 1], [12, 10, 8] and [3, 11, 15, 9, 7, 4] are sharpened; 
  * The arrays [2, 8, 2, 8, 6, 5], [0, 1, 1, 0] and [2, 5, 6, 9, 8, 8] are not sharpened. 



You can do the following operation as many times as you want: choose any strictly positive element of the array, and decrease it by one. Formally, you can choose any i (1 ≤ i ≤ n) such that a_i>0 and assign a_i := a_i - 1.

Tell if it's possible to make the given array sharpened using some number (possibly zero) of these operations.

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 15\ 000) — 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 ≤ n ≤ 3 ⋅ 10^5).

The second line of each test case contains a sequence of n non-negative integers a_1, …, a_n (0 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case, output a single line containing "Yes" (without quotes) if it's possible to make the given array sharpened using the described operations, or "No" (without quotes) otherwise.

Example

Input


10
1
248618
3
12 10 8
6
100 11 15 9 7 8
4
0 1 1 0
2
0 0
2
0 1
2
1 0
2
1 1
3
0 1 0
3
1 0 1


Output


Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No

Note

In the first and the second test case of the first test, the given array is already sharpened.

In the third test case of the first test, we can transform the array into [3, 11, 15, 9, 7, 4] (decrease the first element 97 times and decrease the last element 4 times). It is sharpened because 3 < 11 < 15 and 15 > 9 > 7 > 4.

In the fourth test case of the first test, it's impossible to make the given array sharpened.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kuro has recently won the "Most intelligent cat ever" contest. The three friends then decided to go to Katie's home to celebrate Kuro's winning. After a big meal, they took a small break then started playing games.

Kuro challenged Katie to create a game with only a white paper, a pencil, a pair of scissors and a lot of arrows (you can assume that the number of arrows is infinite). Immediately, Katie came up with the game called Topological Parity.

The paper is divided into $n$ pieces enumerated from $1$ to $n$. Shiro has painted some pieces with some color. Specifically, the $i$-th piece has color $c_{i}$ where $c_{i} = 0$ defines black color, $c_{i} = 1$ defines white color and $c_{i} = -1$ means that the piece hasn't been colored yet.

The rules of the game is simple. Players must put some arrows between some pairs of different pieces in such a way that for each arrow, the number in the piece it starts from is less than the number of the piece it ends at. Also, two different pieces can only be connected by at most one arrow. After that the players must choose the color ($0$ or $1$) for each of the unpainted pieces. The score of a valid way of putting the arrows and coloring pieces is defined as the number of paths of pieces of alternating colors. For example, $[1 \to 0 \to 1 \to 0]$, $[0 \to 1 \to 0 \to 1]$, $[1]$, $[0]$ are valid paths and will be counted. You can only travel from piece $x$ to piece $y$ if and only if there is an arrow from $x$ to $y$.

But Kuro is not fun yet. He loves parity. Let's call his favorite parity $p$ where $p = 0$ stands for "even" and $p = 1$ stands for "odd". He wants to put the arrows and choose colors in such a way that the score has the parity of $p$.

It seems like there will be so many ways which satisfy Kuro. He wants to count the number of them but this could be a very large number. Let's help him with his problem, but print it modulo $10^{9} + 7$.


-----Input-----

The first line contains two integers $n$ and $p$ ($1 \leq n \leq 50$, $0 \leq p \leq 1$) — the number of pieces and Kuro's wanted parity.

The second line contains $n$ integers $c_{1}, c_{2}, ..., c_{n}$ ($-1 \leq c_{i} \leq 1$) — the colors of the pieces.


-----Output-----

Print a single integer — the number of ways to put the arrows and choose colors so the number of valid paths of alternating colors has the parity of $p$.


-----Examples-----
Input
3 1
-1 0 1

Output
6
Input
2 1
1 0

Output
1
Input
1 1
-1

Output
2


-----Note-----

In the first example, there are $6$ ways to color the pieces and add the arrows, as are shown in the figure below. The scores are $3, 3, 5$ for the first row and $5, 3, 3$ for the second row, both from left to right.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sequence of matrices, find the most efficient way to multiply these matrices together. The efficient way is the one that involves the least number of multiplications. 
The dimensions of the matrices are given in an array arr[] of size N (such that N = number of matrices + 1) where the i^{th} matrix has the dimensions (arr[i-1] x arr[i]).
Example 1:
Input: N = 5
arr = {40, 20, 30, 10, 30}
Output: 26000
Explaination: There are 4 matrices of dimension 
40x20, 20x30, 30x10, 10x30. Say the matrices are 
named as A, B, C, D. Out of all possible combinations,
the most efficient way is (A*(B*C))*D. 
The number of operations are -
20*30*10 + 40*20*10 + 40*10*30 = 26000.
Example 2:
Input: N = 4
arr = {10, 30, 5, 60}
Output: 4500
Explaination: The matrices have dimensions 
10*30, 30*5, 5*60. Say the matrices are A, B 
and C. Out of all possible combinations,the
most efficient way is (A*B)*C. The 
number of multiplications are -
10*30*5 + 10*5*60 = 4500.
Your Task:
You do not need to take input or print anything. Your task is to complete the function matrixMultiplication() which takes the value N and the array arr[] as input parameters and returns the minimum number of multiplication operations needed to be performed.
Expected Time Complexity: O(N^{3})
Expected Auxiliary Space: O(N^{2})
Constraints: 
2 ≤ N ≤ 100
1 ≤ arr[i] ≤ 500

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a sequence A of N non-negative integers.
Compute the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i} over all sequences B of N non-negative integers whose sum is at most M, and print it modulo (10^9 + 7).
Here, \dbinom{B_i}{A_i}, the binomial coefficient, denotes the number of ways to choose A_i objects from B_i objects, and is 0 when B_i < A_i.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2000
 - 1 \leq M \leq 10^9
 - 0 \leq A_i \leq 2000

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 A_2 \ldots A_N

-----Output-----
Print the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i}, modulo (10^9 + 7).

-----Sample Input-----
3 5
1 2 1

-----Sample Output-----
8

There are four sequences B such that \prod _{i = 1} ^N \dbinom{B_i}{A_i} is at least 1:
 - B = \{1, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1;
 - B = \{2, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2;
 - B = \{1, 3, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3;
 - B = \{1, 2, 2\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2.
The sum of these is 1 + 2 + 3 + 2 = 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luke is daydreaming in Math class. He has a sheet of graph paper with $n$ rows and $m$ columns, and he imagines that there is an army base in each cell for a total of $n\cdot m$ bases. He wants to drop supplies at strategic points on the sheet, marking each drop point with a red dot. If a base contains at least one package inside or on top of its border fence, then it's considered to be supplied. For example:

Given $n$ and $m$, what's the minimum number of packages that Luke must drop to supply all of his bases?  

Example 

$n=2$ 

$m=3$  

Packages can be dropped at the corner between cells (0, 0), (0, 1), (1, 0) and (1, 1) to supply ${4}$ bases.  Another package can be dropped at a border between (0, 2) and (1, 2).  This supplies all bases using $2$ packages.  

Function Description  

Complete the gameWithCells function in the editor below.  

gameWithCells has the following parameters:  

int n: the number of rows in the game  
int m: the number of columns in the game  

Returns  

int: the minimum number of packages required  

Input Format

Two space-separated integers describing the respective values of $n$ and $m$.

Constraints

$0<n,m\leq1000$  

Sample Input 0
2 2

Sample Output 0
1

Explanation 0

Luke has four bases in a $2\times2$ grid. If he drops a single package where the walls of all four bases intersect, then those four cells can access the package:

Because he managed to supply all four bases with a single supply drop, we print ${1}$ as our answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a non-empty string s=s_1s_2... s_n, which consists only of lowercase Latin letters. Polycarp does not like a string if it contains at least one string "one" or at least one string "two" (or both at the same time) as a substring. In other words, Polycarp does not like the string s if there is an integer j (1 ≤ j ≤ n-2), that s_{j}s_{j+1}s_{j+2}="one" or s_{j}s_{j+1}s_{j+2}="two".

For example:

  * Polycarp does not like strings "oneee", "ontwow", "twone" and "oneonetwo" (they all have at least one substring "one" or "two"), 
  * Polycarp likes strings "oonnee", "twwwo" and "twnoe" (they have no substrings "one" and "two"). 



Polycarp wants to select a certain set of indices (positions) and remove all letters on these positions. All removals are made at the same time.

For example, if the string looks like s="onetwone", then if Polycarp selects two indices 3 and 6, then "onetwone" will be selected and the result is "ontwne".

What is the minimum number of indices (positions) that Polycarp needs to select to make the string liked? What should these positions be?

Input

The first line of the input contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases in the input. Next, the test cases are given.

Each test case consists of one non-empty string s. Its length does not exceed 1.5⋅10^5. The string s consists only of lowercase Latin letters.

It is guaranteed that the sum of lengths of all lines for all input data in the test does not exceed 1.5⋅10^6.

Output

Print an answer for each test case in the input in order of their appearance.

The first line of each answer should contain r (0 ≤ r ≤ |s|) — the required minimum number of positions to be removed, where |s| is the length of the given line. The second line of each answer should contain r different integers — the indices themselves for removal in any order. Indices are numbered from left to right from 1 to the length of the string. If r=0, then the second line can be skipped (or you can print empty). If there are several answers, print any of them.

Examples

Input


4
onetwone
testme
oneoneone
twotwo


Output


2
6 3
0

3
4 1 7 
2
1 4


Input


10
onetwonetwooneooonetwooo
two
one
twooooo
ttttwo
ttwwoo
ooone
onnne
oneeeee
oneeeeeeetwooooo


Output


6
18 11 12 1 6 21 
1
1 
1
3 
1
2 
1
6 
0

1
4 
0

1
1 
2
1 11 

Note

In the first example, answers are:

  * "onetwone", 
  * "testme" — Polycarp likes it, there is nothing to remove, 
  * "oneoneone", 
  * "twotwo". 



In the second example, answers are: 

  * "onetwonetwooneooonetwooo", 
  * "two", 
  * "one", 
  * "twooooo", 
  * "ttttwo", 
  * "ttwwoo" — Polycarp likes it, there is nothing to remove, 
  * "ooone", 
  * "onnne" — Polycarp likes it, there is nothing to remove, 
  * "oneeeee", 
  * "oneeeeeeetwooooo". 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A rare article in the Internet is posted without a possibility to comment it. On a Polycarp's website each article has comments feed.

Each comment on Polycarp's website is a non-empty string consisting of uppercase and lowercase letters of English alphabet. Comments have tree-like structure, that means each comment except root comments (comments of the highest level) has exactly one parent comment.

When Polycarp wants to save comments to his hard drive he uses the following format. Each comment he writes in the following format:   at first, the text of the comment is written;  after that the number of comments is written, for which this comment is a parent comment (i. e. the number of the replies to this comments);  after that the comments for which this comment is a parent comment are written (the writing of these comments uses the same algorithm).  All elements in this format are separated by single comma. Similarly, the comments of the first level are separated by comma.

For example, if the comments look like: [Image] 

then the first comment is written as "hello,2,ok,0,bye,0", the second is written as "test,0", the third comment is written as "one,1,two,2,a,0,b,0". The whole comments feed is written as: "hello,2,ok,0,bye,0,test,0,one,1,two,2,a,0,b,0". For a given comments feed in the format specified above print the comments in a different format:   at first, print a integer d — the maximum depth of nesting comments;  after that print d lines, the i-th of them corresponds to nesting level i;  for the i-th row print comments of nesting level i in the order of their appearance in the Policarp's comments feed, separated by space. 


-----Input-----

The first line contains non-empty comments feed in the described format. It consists of uppercase and lowercase letters of English alphabet, digits and commas. 

It is guaranteed that each comment is a non-empty string consisting of uppercase and lowercase English characters. Each of the number of comments is integer (consisting of at least one digit), and either equals 0 or does not contain leading zeros.

The length of the whole string does not exceed 10^6. It is guaranteed that given structure of comments is valid. 


-----Output-----

Print comments in a format that is given in the statement. For each level of nesting, comments should be printed in the order they are given in the input.


-----Examples-----
Input
hello,2,ok,0,bye,0,test,0,one,1,two,2,a,0,b,0

Output
3
hello test one 
ok bye two 
a b 



Input
a,5,A,0,a,0,A,0,a,0,A,0

Output
2
a 
A a A a A 



Input
A,3,B,2,C,0,D,1,E,0,F,1,G,0,H,1,I,1,J,0,K,1,L,0,M,2,N,0,O,1,P,0

Output
4
A K M 
B F H L N O 
C D G I P 
E J 




-----Note-----

The first example is explained in the statements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.


 
Example 1:
Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
 
Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your colleagues have been good enough(?) to buy you a birthday gift. Even though it is your birthday and not theirs, they have decided to play pass the parcel with it so that everyone has an even chance of winning. There are multiple presents, and you will receive one, but not all are nice... One even explodes and covers you in soil... strange office. To make up for this one present is a dog! Happy days! (do not buy dogs as presents, and if you do, never wrap them).

Depending on the number of passes in the game (y), and the present you unwrap (x), return as follows:

x == goodpresent --> return x with num of passes added to each charCode (turn to charCode, add y to each, turn back)
x == crap || x == empty --> return string sorted alphabetically
x == bang --> return string turned to char codes, each code reduced by number of passes and summed to a single figure
x == badpresent --> return 'Take this back!'
x == dog, return 'pass out from excitement y times' (where y is the value given for y).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Berland consists of n cities and m bidirectional roads connecting pairs of cities. There is no road connecting a city to itself, and between any pair of cities there is no more than one road. It is possible to reach any city from any other moving along roads.

Currently Mr. President is in the city s and his destination is the city t. He plans to move along roads from s to t (s ≠ t).

That's why Ministry of Fools and Roads has difficult days. The minister is afraid that Mr. President could get into a traffic jam or get lost. Who knows what else can happen!

To be sure that everything goes as planned, the minister decided to temporarily make all roads one-way. So each road will be oriented in one of two possible directions. The following conditions must be satisfied:

  * There should be no cycles along roads after orientation. 
  * The city s should be the only such city that all its roads are oriented out (i.e. there are no ingoing roads to the city s and the city s is the only such city). 
  * The city t should be the only such city that all its roads are oriented in (i.e. there are no outgoing roads from the city t and the city t is the only such city). 



Help the minister solve his problem. Write a program to find any such orientation of all roads or report that no solution exists.

Input

Each test in this problem contains one or more test cases to solve. The first line of the input contains positive number T — the number of cases to solve.

Each case starts with a line containing four integers n, m, s and t (2 ≤ n ≤ 4·105, 1 ≤ m ≤ 106, 1 ≤ s, t ≤ n, s ≠ t) — the number of cities, the number of roads and indices of departure and destination cities. The cities are numbered from 1 to n.

The following m lines contain roads, one road per line. Each road is given as two integer numbers xj, yj (1 ≤ xj, yj ≤ n, xj ≠ yj), which means that the j-th road connects cities xj and yj. There is at most one road between any pair of cities. It is possible to reach any city from any other moving along roads.

The sum of values n over all cases in a test doesn't exceed 4·105. The sum of values m over all cases in a test doesn't exceed 106.

Output

For each case print "Yes" if the answer exists. In the following m lines print roads in the required directions. You can print roads in arbitrary order. If there are multiple answers, print any of them.

Print the only line "No" if there is no answer for a case.

Example

Input

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


Output

Yes
1 2
3 2
4 3
1 4
No

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