vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
#Permutation  position
In this kata you will have to permutate through a string of lowercase letters, each permutation will start at ```a``` and you must calculate how many iterations it takes to reach the current permutation.

##examples
```
input: 'a'
result: 1

input: 'c'
result: 3

input: 'z'
result: 26

input: 'foo'
result: 3759

input: 'aba'
result: 27

input: 'abb'
result: 28

```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence a1, a2, ..., an consisting of different integers. It is required to split this sequence into the maximum number of subsequences such that after sorting integers in each of them in increasing order, the total sequence also will be sorted in increasing order.

Sorting integers in a subsequence is a process such that the numbers included in a subsequence are ordered in increasing order, and the numbers which are not included in a subsequence don't change their places.

Every element of the sequence must appear in exactly one subsequence.

Input

The first line of input data contains integer n (1 ≤ n ≤ 105) — the length of the sequence.

The second line of input data contains n different integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the elements of the sequence. It is guaranteed that all elements of the sequence are distinct.

Output

In the first line print the maximum number of subsequences k, which the original sequence can be split into while fulfilling the requirements.

In the next k lines print the description of subsequences in the following format: the number of elements in subsequence ci (0 < ci ≤ n), then ci integers l1, l2, ..., lci (1 ≤ lj ≤ n) — indices of these elements in the original sequence. 

Indices could be printed in any order. Every index from 1 to n must appear in output exactly once.

If there are several possible answers, print any of them.

Examples

Input

6
3 2 1 6 5 4


Output

4
2 1 3
1 2
2 4 6
1 5


Input

6
83 -75 -49 11 37 62


Output

1
6 1 2 3 4 5 6

Note

In the first sample output:

After sorting the first subsequence we will get sequence 1 2 3 6 5 4.

Sorting the second subsequence changes nothing.

After sorting the third subsequence we will get sequence 1 2 3 4 5 6.

Sorting the last subsequence changes nothing.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call an undirected graph of n vertices p-interesting, if the following conditions fulfill:   the graph contains exactly 2n + p edges;  the graph doesn't contain self-loops and multiple edges;  for any integer k (1 ≤ k ≤ n), any subgraph consisting of k vertices contains at most 2k + p edges. 

A subgraph of a graph is some set of the graph vertices and some set of the graph edges. At that, the set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices. 

Your task is to find a p-interesting graph consisting of n vertices.


-----Input-----

The first line contains a single integer t (1 ≤ t ≤ 5) — the number of tests in the input. Next t lines each contains two space-separated integers: n, p (5 ≤ n ≤ 24; p ≥ 0; $2 n + p \leq \frac{n(n - 1)}{2}$) — the number of vertices in the graph and the interest value for the appropriate test. 

It is guaranteed that the required graph exists.


-----Output-----

For each of the t tests print 2n + p lines containing the description of the edges of a p-interesting graph: the i-th line must contain two space-separated integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}) — two vertices, connected by an edge in the resulting graph. Consider the graph vertices numbered with integers from 1 to n. 

Print the answers to the tests in the order the tests occur in the input. If there are multiple solutions, you can print any of them.


-----Examples-----
Input
1
6 0

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Next Test

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
«Polygon» is a system which allows to create programming tasks in a simple and professional way. When you add a test to the problem, the corresponding form asks you for the test index. As in most cases it is clear which index the next test will have, the system suggests the default value of the index. It is calculated as the smallest positive integer which is not used as an index for some previously added test.

You are to implement this feature. Create a program which determines the default index of the next test, given the indexes of the previously added tests.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=3000) — the amount of previously added tests. The second line contains *n* distinct integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=3000) — indexes of these tests.

Output Specification:
Output the required default value for the next test index.

Demo Input:
['3\n1 7 2\n']

Demo Output:
['3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Implication is a function of two logical arguments, its value is false if and only if the value of the first argument is true and the value of the second argument is false. 

Implication is written by using character '$\rightarrow$', and the arguments and the result of the implication are written as '0' (false) and '1' (true). According to the definition of the implication: 

$0 \rightarrow 0 = 1$ 

$0 \rightarrow 1 = 1$

$1 \rightarrow 0 = 0$ 

$1 \rightarrow 1 = 1$

When a logical expression contains multiple implications, then when there are no brackets, it will be calculated from left to fight. For example,

$0 \rightarrow 0 \rightarrow 0 =(0 \rightarrow 0) \rightarrow 0 = 1 \rightarrow 0 = 0$. 

When there are brackets, we first calculate the expression in brackets. For example,

$0 \rightarrow(0 \rightarrow 0) = 0 \rightarrow 1 = 1$.

For the given logical expression $a_{1} \rightarrow a_{2} \rightarrow a_{3} \rightarrow \cdots \cdots a_{n}$ determine if it is possible to place there brackets so that the value of a logical expression is false. If it is possible, your task is to find such an arrangement of brackets.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100 000) — the number of arguments in a logical expression.

The second line contains n numbers a_1, a_2, ..., a_{n} ($a_{i} \in \{0,1 \}$), which means the values of arguments in the expression in the order they occur.


-----Output-----

Print "NO" (without the quotes), if it is impossible to place brackets in the expression so that its value was equal to 0.

Otherwise, print "YES" in the first line and the logical expression with the required arrangement of brackets in the second line.

The expression should only contain characters '0', '1', '-' (character with ASCII code 45), '>' (character with ASCII code 62), '(' and ')'. Characters '-' and '>' can occur in an expression only paired like that: ("->") and represent implication. The total number of logical arguments (i.e. digits '0' and '1') in the expression must be equal to n. The order in which the digits follow in the expression from left to right must coincide with a_1, a_2, ..., a_{n}.

The expression should be correct. More formally, a correct expression is determined as follows:  Expressions "0", "1" (without the quotes) are correct.  If v_1, v_2 are correct, then v_1->v_2 is a correct expression.  If v is a correct expression, then (v) is a correct expression. 

The total number of characters in the resulting expression mustn't exceed 10^6.

If there are multiple possible answers, you are allowed to print any of them.


-----Examples-----
Input
4
0 1 1 0

Output
YES
(((0)->1)->(1->0))

Input
2
1 1

Output
NO

Input
1
0

Output
YES
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Greg and Array

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Greg has an array *a*<==<=*a*1,<=*a*2,<=...,<=*a**n* and *m* operations. Each operation looks as: *l**i*, *r**i*, *d**i*, (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*). To apply operation *i* to the array means to increase all array elements with numbers *l**i*,<=*l**i*<=+<=1,<=...,<=*r**i* by value *d**i*.

Greg wrote down *k* queries on a piece of paper. Each query has the following form: *x**i*, *y**i*, (1<=≤<=*x**i*<=≤<=*y**i*<=≤<=*m*). That means that one should apply operations with numbers *x**i*,<=*x**i*<=+<=1,<=...,<=*y**i* to the array.

Now Greg is wondering, what the array *a* will be after all the queries are executed. Help Greg.

Input Specification:
The first line contains integers *n*, *m*, *k* (1<=≤<=*n*,<=*m*,<=*k*<=≤<=105). The second line contains *n* integers: *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=105) — the initial array.

Next *m* lines contain operations, the operation number *i* is written as three integers: *l**i*, *r**i*, *d**i*, (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*), (0<=≤<=*d**i*<=≤<=105).

Next *k* lines contain the queries, the query number *i* is written as two integers: *x**i*, *y**i*, (1<=≤<=*x**i*<=≤<=*y**i*<=≤<=*m*).

The numbers in the lines are separated by single spaces.

Output Specification:
On a single line print *n* integers *a*1,<=*a*2,<=...,<=*a**n* — the array after executing all the queries. Separate the printed numbers by spaces.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.

Demo Input:
['3 3 3\n1 2 3\n1 2 1\n1 3 2\n2 3 4\n1 2\n1 3\n2 3\n', '1 1 1\n1\n1 1 1\n1 1\n', '4 3 6\n1 2 3 4\n1 2 1\n2 3 2\n3 4 4\n1 2\n1 3\n2 3\n1 2\n1 3\n2 3\n']

Demo Output:
['9 18 17\n', '2\n', '5 18 31 20\n']

Note:
none

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

Chocolate company Chinor Choco has decided to build n new stores.
For each store, ask each store manager to prepare two candidates for the place you want to build, and build it in either place.

Chinor Choco sells m types of chocolate, each manufactured at a different factory.
All types of chocolate are sold at all stores.
Chinor Choco owns only one truck to transport chocolate, and one truck can only carry one store's worth of chocolate.
Therefore, trucks need to go around all factories when moving from one store to another.

Find the maximum travel distance when the stores are arranged so that the maximum minimum travel distance when moving from one store to another is the minimum.

There can be multiple stores and factories in the same location.

Constraints

The input satisfies the following conditions.

* 2 ≤ n ≤ 200
* 1 ≤ m ≤ 15
* 0 ≤ ai, bi, ci, di, xi, yi ≤ 1000

Input

The input is given in the following format.


n m
a0 b0 c0 d0
...
an−1 bn−1 cn−1 dn−1
x0 y0
...
xm−1 ym−1


All inputs are given as integers.
On the first line, the number of Chinor chocolate shops n and the number of chocolate manufacturing factories m are given, separated by blanks.
From the second line to the nth line, the coordinates (ai, bi), (ci, di) of the candidate places to build each store are given separated by blanks.
2 & plus; Factory coordinates (xi, yi) are given from the nth line to the mth line, separated by blanks.

Output

Output the maximum travel distance when the store is arranged so that the maximum of the minimum travel distance is minimized.
The error should not exceed 10-6.

Examples

Input

2 1
0 0 5 5
3 3 6 6
2 2


Output

4.2426406871


Input

2 2
0 0 6 0
7 0 3 0
4 0
5 0


Output

3.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima's spent much time thinking what present to give to Inna and gave her an empty sequence w. Now they want to fill sequence w with numbers zero and one. For that, they decided to play an amusing game. 

Before the game begins, Dima chooses m integers a1, a2, ..., am (1 ≤ a1 < a2 < ... < am). Then Inna and Dima start playing, that is, adding numbers to sequence w. Each new number they choose is added to the end of the sequence. At some moments of time Dima feels that the game is going to end too soon (and he wants to play with Inna as long as possible), so he hits a table hard with his fist. At that the a1-th, a2-th, a3-th, ..., ak-th numbers from the beginning simultaneously fall out of the sequence (the sequence gets k numbers less). Here k is such maximum number that value ak doesn't exceed the current length of the sequence. If number a1 is larger than the current length of w, then nothing falls out of the sequence.

You are given the chronological sequence of events in the game. Each event is either adding a number to the end of sequence w or Dima's hit on the table. Calculate the sequence w after all these events happen.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 106) showing how many events took place and how many numbers Dima chose.

The next line contains m distinct integers ai (1 ≤ ai ≤ 106) sorted in the increasing order. 

Next n lines describe the events in the chronological order. Each line contains a single integer: -1, 0 or 1. Number -1 means that Dima hits the table. Number 0 means that Inna and Dima add number 0 to the end of the sequence. Number 1 means that Inna and Dima add number 1 to the end of the sequence.

Output

In a single line print a sequence of numbers 0 and 1 — the elements of the sequence after all events happen. Print the elements of the sequence in the order from the beginning to the end of the sequence.

If after all events the sequence ends up empty, print "Poor stack!".

Examples

Input

10 3
1 3 6
-1
1
1
0
0
-1
0
1
-1
1


Output

011


Input

2 1
1
1
-1


Output

Poor stack!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has started watching football games. He has learned that for some fouls the players receive yellow cards, and for some fouls they receive red cards. A player who receives the second yellow card automatically receives a red card.

Vasya is watching a recorded football match now and makes notes of all the fouls that he would give a card for. Help Vasya determine all the moments in time when players would be given red cards if Vasya were the judge. For each player, Vasya wants to know only the first moment of time when he would receive a red card from Vasya.

Input

The first line contains the name of the team playing at home. The second line contains the name of the team playing away. Both lines are not empty. The lengths of both lines do not exceed 20. Each line contains only of large English letters. The names of the teams are distinct.

Next follows number n (1 ≤ n ≤ 90) — the number of fouls. 

Each of the following n lines contains information about a foul in the following form: 

  * first goes number t (1 ≤ t ≤ 90) — the minute when the foul occurs; 
  * then goes letter "h" or letter "a" — if the letter is "h", then the card was given to a home team player, otherwise the card was given to an away team player; 
  * then goes the player's number m (1 ≤ m ≤ 99); 
  * then goes letter "y" or letter "r" — if the letter is "y", that means that the yellow card was given, otherwise the red card was given. 



The players from different teams can have the same number. The players within one team have distinct numbers. The fouls go chronologically, no two fouls happened at the same minute.

Output

For each event when a player received his first red card in a chronological order print a string containing the following information:

  * The name of the team to which the player belongs; 
  * the player's number in his team; 
  * the minute when he received the card. 



If no player received a card, then you do not need to print anything.

It is possible case that the program will not print anything to the output (if there were no red cards).

Examples

Input

MC
CSKA
9
28 a 3 y
62 h 25 y
66 h 42 y
70 h 25 y
77 a 4 y
79 a 25 y
82 h 42 r
89 h 16 y
90 a 13 r


Output

MC 25 70
MC 42 82
CSKA 13 90

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is lunch time at the Vibrant Gujarat Summit and all the investors are called for the executive lunch. When Bruce reached the lunch area, he found that the waiter was taking out bowls from a big box containing some amount of golden bowls and other bronze bowls. The bowls were taken out at random. Each dish contains exactly one bowl. Bruce and Robin are the first ones to receive the dishes.

Bruce believes that there is a 50/50 chance in everything. He tells Robin that the there is a 50% chance of both of them receiving a golden bowl. Robin is confused and doesn't know how is that possible. He asks Bruce what makes him think so. Bruce says that he would have to find the answer himself and so in order to make things interesting he tells Robin the total number of bowls the waiter has in the box. All Robin has to do is now find the number of golden bowls there should be in the box in order for it to be a 50% probability.

Input:
Only one integer number, N, telling the number of bowls in the box.

Output:
 The number of golden bowls required for it to be a 50% probability of both of them receiving a golden bowl.

Constraints:
 1 ≤ N ≤ 10^15

SAMPLE INPUT
21

SAMPLE OUTPUT
15

Explanation

As Bruce and Robin are the first ones to receive the bowls, if there are 15 golden bowls then the probability for the first person to get a golden one is 15/21 and the second one is 14/20.

(15/21)*(14/20) = 0.5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Illiteracy is a simple puzzle game created by Le Sio. 1 The game consists of a sequence of eight icons; the actual icons are very artistic, but for simplicity, we’ll label the icons using a capital letter A—F. Clicking any icon has a unique effect on the other icons, based on which icon is clicked and that icon’s position in the sequence. Most of the icons rotate the type of other icons. A rotation changes an A to a B, B to C, C to D, D to E, E to F, and F back to A.

Here’s what the icons do when you click on one, based on the type of the icon and its position $x$ in the sequence ($1\leq x \leq 8$):

Type

Effect

A

Rotates the icons immediately to the left and right (at positions $x-1$ and $x+1$), ignoring any icon that doesn’t exist (when $x=1$ or $8$).

B

If the icon is at either end of the sequence, does nothing. Otherwise, changes the icon at position $x+1$ to the same type as the current icon at $x-1$.

C

Rotates the icon at position $9-x$.

D

Rotates all icons between position $x$ and the closest of the sequence’s two ends. (Does nothing if $x$ is one of the two ends, and does not change the icon at position $x$ itself). For example, if $x=3$, the icons at $x=1$ and $2$ would be rotated. If $x=5$, then the icons at positions $6$, $7$, and $8$ would be rotated.

E

If the icon is at either end of the sequence, does nothing. Otherwise, let $y$ be the number of icons between position $x$ and the closest of the sequence’s two ends. Rotates the two icons at positions $x-y$ and $x+y$. For example, if $x=3$, the icons at $x=1$ and $5$ would be rotated. If $x=5$, the icons at positions $8$ and $2$ would be rotated.

F

If $x$ is odd, rotates the icon at position $(x+9)/2$. If $x$ is even, rotates the icon at position $x/2$.

Given a starting sequence of icons and a target sequence, what is the minimal number of clicks required to transform the starting sequence into the target sequence?Examples

For the cases below, we illustrate one possible minimal sequence of clicks to get from the top configuration to the bottom one. The carets indicate which icon on the previous line was clicked to generate the sequence on the following line. The sequence on the left takes $2$ clicks; the sequence on the right takes $4$ clicks.

ABCDEFCD        DCDAFCBA ^      ^   
BCDDEFCD        DCEAACBA ^       ^
BCEDEFCD        DCEAACBC ^      DCEAACCC ^     ECEABCCC


-----Input-----
The input consists of exactly two lines of eight characters each. The first line is the starting icon sequence, and the second is the target sequence. Each character on each line is one of the six capital letters A, B, C, D, E, or F. It will always be possible to reach the target sequence from the given starting sequence using a finite number of clicks.

-----Output-----
Output a single integer, the smallest number of icon clicks needed to get from the starting sequence to the target sequence.

-----Examples-----
Sample Input 1:
ABCDEFCD
BCEDEFCD
Sample Output 1:
2

Sample Input 2:
DCDAFCBA
ECEABCCC
Sample Output 2:
4

Sample Input 3:
ABCDEFCD
ABCDEFCD
Sample Output 3:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob really likes playing with arrays of numbers. That's why for his birthday, his friends bought him a really interesting machine – an array beautifier. 

The array beautifier takes an array A consisting of N integers, and it outputs a new array B of length N that it constructed based on the array given to it. The array beautifier constructs the new array in the following way: it takes two numbers at different indices from the original array and writes their sum to the end of the new array. It does this step N times - resulting in an output array of length N. During this process, the machine can take the same index multiple times in different steps. 

Bob was very excited about the gift that his friends gave him, so he put his favorite array in the machine. However, when the machine finished, Bob was not happy with the resulting array. He misses his favorite array very much, and hopes to get it back. 

Given the array that the machine outputted, help Bob find an array that could be the original array that he put in the machine. Sometimes the machine makes mistakes, so it is possible that no appropriate input array exists for the array it has outputted. In such case, let Bob know that his array is forever lost.

Input

The first line contains one positive integer N (2 ≤ N ≤ 10^3) – the length of Bob's array.

The second line contains N integers B_1, B_2, ..., B_N (1 ≤ B_i ≤ 10^6) – the elements of the array the machine outputted.

Output

If an appropriate input array exists, print "YES", followed by the input array A_1, A_2, ..., A_N (-10^9 ≤ A_i ≤ 10^9) in the next line. Otherwise, print "NO".

Examples

Input


2
5 5


Output


YES
2 3


Input


3
1 2 3


Output


YES
0 1 2


Input


3
2 4 5


Output


NO


Input


4
1 3 5 7


Output


YES
6 -3 4 1

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