vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Cat Furrier Transform is a popular algorithm among cat programmers to create longcats. As one of the greatest cat programmers ever exist, Neko wants to utilize this algorithm to create the perfect longcat.

Assume that we have a cat with a number $x$. A perfect longcat is a cat with a number equal $2^m - 1$ for some non-negative integer $m$. For example, the numbers $0$, $1$, $3$, $7$, $15$ and so on are suitable for the perfect longcats.

In the Cat Furrier Transform, the following operations can be performed on $x$:  (Operation A): you select any non-negative integer $n$ and replace $x$ with $x \oplus (2^n - 1)$, with $\oplus$ being a bitwise XOR operator. (Operation B): replace $x$ with $x + 1$. 

The first applied operation must be of type A, the second of type B, the third of type A again, and so on. Formally, if we number operations from one in the order they are executed, then odd-numbered operations must be of type A and the even-numbered operations must be of type B.

Neko wants to produce perfect longcats at industrial scale, thus for each cat Neko only wants to perform at most $40$ operations. Can you help Neko writing a transformation plan?

Note that it is not required to minimize the number of operations. You just need to use no more than $40$ operations.


-----Input-----

The only line contains a single integer $x$ ($1 \le x \le 10^6$).


-----Output-----

The first line should contain a single integer $t$ ($0 \le t \le 40$) — the number of operations to apply.

Then for each odd-numbered operation print the corresponding number $n_i$ in it. That is, print $\lceil \frac{t}{2} \rceil$ integers $n_i$ ($0 \le n_i \le 30$), denoting the replacement $x$ with $x \oplus (2^{n_i} - 1)$ in the corresponding step.

If there are multiple possible answers, you can print any of them. It is possible to show, that there is at least one answer in the constraints of this problem.


-----Examples-----
Input
39

Output
4
5 3 
Input
1

Output
0

Input
7

Output
0



-----Note-----

In the first test, one of the transforms might be as follows: $39 \to 56 \to 57 \to 62 \to 63$. Or more precisely: Pick $n = 5$. $x$ is transformed into $39 \oplus 31$, or $56$.  Increase $x$ by $1$, changing its value to $57$.  Pick $n = 3$. $x$ is transformed into $57 \oplus 7$, or $62$.  Increase $x$ by $1$, changing its value to $63 = 2^6 - 1$. 

In the second and third test, the number already satisfies the goal requirement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a function that takes a Roman numeral as its argument and returns its value as a numeric decimal integer. You don't need to validate the form of the Roman numeral.

Modern Roman numerals are written by expressing each decimal digit of the number to be encoded separately, starting with the leftmost digit and skipping any 0s. So 1990 is rendered "MCMXC" (1000 = M, 900 = CM, 90 = XC) and 2008 is rendered "MMVIII" (2000 = MM, 8 = VIII). The Roman numeral for 1666, "MDCLXVI", uses each letter in descending order.

Example:

```python
solution('XXI') # should return 21
```

```Elixir
Solution.decode("XXI") # should return 21
```

Help:
```
Symbol  Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1,000
```

*Courtesy of rosettacode.org*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Ilya and Bank Account

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ilya is a very clever lion, he lives in an unusual city ZooVille. In this city all the animals have their rights and obligations. Moreover, they even have their own bank accounts. The state of a bank account is an integer. The state of a bank account can be a negative number. This means that the owner of the account owes the bank money.

Ilya the Lion has recently had a birthday, so he got a lot of gifts. One of them (the gift of the main ZooVille bank) is the opportunity to delete the last digit or the digit before last from the state of his bank account no more than once. For example, if the state of Ilya's bank account is -123, then Ilya can delete the last digit and get his account balance equal to -12, also he can remove its digit before last and get the account balance equal to -13. Of course, Ilya is permitted not to use the opportunity to delete a digit from the balance.

Ilya is not very good at math, and that's why he asks you to help him maximize his bank account. Find the maximum state of the bank account that can be obtained using the bank's gift.

Input Specification:
The single line contains integer *n* (10<=≤<=|*n*|<=≤<=109) — the state of Ilya's bank account.

Output Specification:
In a single line print an integer — the maximum state of the bank account that Ilya can get.

Demo Input:
['2230\n', '-10\n', '-100003\n']

Demo Output:
['2230\n', '0\n', '-10000\n']

Note:
In the first test sample Ilya doesn't profit from using the present.

In the second test sample you can delete digit 1 and get the state of the account equal to 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tzuyu gave Nayeon a strip of $N$ cells (numbered $1$ through $N$) for her birthday. This strip is described by a sequence $A_1, A_2, \ldots, A_N$, where for each valid $i$, the $i$-th cell is blocked if $A_i = 1$ or free if $A_i = 0$. Tzuyu and Nayeon are going to use it to play a game with the following rules:
- The players alternate turns; Nayeon plays first.
- Initially, both players are outside of the strip. However, note that afterwards during the game, their positions are always different.
- In each turn, the current player should choose a free cell and move there. Afterwards, this cell becomes blocked and the players cannot move to it again.
- If it is the current player's first turn, she may move to any free cell.
- Otherwise, she may only move to one of the left and right adjacent cells, i.e. from a cell $c$, the current player may only move to the cell $c-1$ or $c+1$ (if it is free).
- If a player is unable to move to a free cell during her turn, this player loses the game.
Nayeon and Tzuyu are very smart, so they both play optimally. Since it is Nayeon's birthday, she wants to know if she can beat Tzuyu. Find out who wins.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing the string "Yes" if Nayeon wins the game or "No" if Tzuyu wins (without quotes).

-----Constraints-----
- $1 \le T \le 40,000$
- $2 \le N \le 3\cdot 10^5$
- $0 \le A_i \le 1$ for each valid $i$
- $A_1 = A_N = 1$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points): $A_i = 0$ for each $i$ ($2 \le i \le N-1$)
Subtask #2 (50 points): original constraints

-----Example Input-----
4
7
1 1 0 0 0 1 1
8
1 0 1 1 1 0 0 1
4
1 1 0 1
4
1 1 1 1

-----Example Output-----
Yes
No
Yes
No

-----Explanation-----
Example case 1: Since both Nayeon and Tzuyu play optimally, Nayeon can start e.g. by moving to cell $4$, which then becomes blocked. Tzuyu has to pick either the cell $3$ or the cell $5$, which also becomes blocked. Nayeon is then left with only one empty cell next to cell $4$ (the one Tzuyu did not pick); after she moves there, Tzuyu is unable to move, so she loses the game.
Example case 2: Regardless of what cell Nayeon moves to at the start, Tzuyu will always be able to beat her.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Manao works on a sports TV. He's spent much time watching the football games of some country. After a while he began to notice different patterns. For example, each team has two sets of uniforms: home uniform and guest uniform. When a team plays a game at home, the players put on the home uniform. When a team plays as a guest on somebody else's stadium, the players put on the guest uniform. The only exception to that rule is: when the home uniform color of the host team matches the guests' uniform, the host team puts on its guest uniform as well. For each team the color of the home and guest uniform is different.

There are n teams taking part in the national championship. The championship consists of n·(n - 1) games: each team invites each other team to its stadium. At this point Manao wondered: how many times during the championship is a host team going to put on the guest uniform? Note that the order of the games does not affect this number.

You know the colors of the home and guest uniform for each team. For simplicity, the colors are numbered by integers in such a way that no two distinct colors have the same number. Help Manao find the answer to his question.


-----Input-----

The first line contains an integer n (2 ≤ n ≤ 30). Each of the following n lines contains a pair of distinct space-separated integers h_{i}, a_{i} (1 ≤ h_{i}, a_{i} ≤ 100) — the colors of the i-th team's home and guest uniforms, respectively.


-----Output-----

In a single line print the number of games where the host team is going to play in the guest uniform.


-----Examples-----
Input
3
1 2
2 4
3 4

Output
1

Input
4
100 42
42 100
5 42
100 5

Output
5

Input
2
1 2
1 2

Output
0



-----Note-----

In the first test case the championship consists of 6 games. The only game with the event in question is the game between teams 2 and 1 on the stadium of team 2.

In the second test sample the host team will have to wear guest uniform in the games between teams: 1 and 2, 2 and 1, 2 and 3, 3 and 4, 4 and 2 (the host team is written first).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a directed graph with $n$ vertices and $m$ directed edges without self-loops or multiple edges.

Let's denote the $k$-coloring of a digraph as following: you color each edge in one of $k$ colors. The $k$-coloring is good if and only if there no cycle formed by edges of same color.

Find a good $k$-coloring of given digraph with minimum possible $k$.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \le n \le 5000$, $1 \le m \le 5000$) — the number of vertices and edges in the digraph, respectively.

Next $m$ lines contain description of edges — one per line. Each edge is a pair of integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — there is directed edge from $u$ to $v$ in the graph.

It is guaranteed that each ordered pair $(u, v)$ appears in the list of edges at most once.


-----Output-----

In the first line print single integer $k$ — the number of used colors in a good $k$-coloring of given graph.

In the second line print $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le k$), where $c_i$ is a color of the $i$-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize $k$).


-----Examples-----
Input
4 5
1 2
1 3
3 4
2 4
1 4

Output
1
1 1 1 1 1 

Input
3 3
1 2
2 3
3 1

Output
2
1 1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Lara Croft and the New Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You might have heard about the next game in Lara Croft series coming out this year. You also might have watched its trailer. Though you definitely missed the main idea about its plot, so let me lift the veil of secrecy.

Lara is going to explore yet another dangerous dungeon. Game designers decided to use good old 2D environment. The dungeon can be represented as a rectangle matrix of *n* rows and *m* columns. Cell (*x*,<=*y*) is the cell in the *x*-th row in the *y*-th column. Lara can move between the neighbouring by side cells in all four directions.

Moreover, she has even chosen the path for herself to avoid all the traps. She enters the dungeon in cell (1,<=1), that is top left corner of the matrix. Then she goes down all the way to cell (*n*,<=1) — the bottom left corner. Then she starts moving in the snake fashion — all the way to the right, one cell up, then to the left to the cell in 2-nd column, one cell up. She moves until she runs out of non-visited cells. *n* and *m* given are such that she always end up in cell (1,<=2).

Lara has already moved to a neighbouring cell *k* times. Can you determine her current position?

Input Specification:
The only line contains three integers *n*, *m* and *k* (2<=≤<=*n*,<=*m*<=≤<=109, *n* is always even, 0<=≤<=*k*<=&lt;<=*n*·*m*). Note that *k* doesn't fit into 32-bit integer type!

Output Specification:
Print the cell (the row and the column where the cell is situated) where Lara ends up after she moves *k* times.

Demo Input:
['4 3 0\n', '4 3 11\n', '4 3 7\n']

Demo Output:
['1 1\n', '1 2\n', '3 2\n']

Note:
Here is her path on matrix 4 by 3:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
_Friday 13th or Black Friday is considered as unlucky day. Calculate how many unlucky days are in the given year._

Find the number of Friday 13th in the given year.

__Input:__ Year as an integer.

__Output:__ Number of Black Fridays in the year as an integer.

__Examples:__

        unluckyDays(2015) == 3
        unluckyDays(1986) == 1

***Note:*** In Ruby years will start from 1593.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ksenia has an array a consisting of n positive integers a_1, a_2, …, a_n. 

In one operation she can do the following: 

  * choose three distinct indices i, j, k, and then 
  * change all of a_i, a_j, a_k to a_i ⊕ a_j ⊕ a_k simultaneously, where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 



She wants to make all a_i equal in at most n operations, or to determine that it is impossible to do so. She wouldn't ask for your help, but please, help her!

Input

The first line contains one integer n (3 ≤ n ≤ 10^5) — the length of a.

The second line contains n integers, a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) — elements of a.

Output

Print YES or NO in the first line depending on whether it is possible to make all elements equal in at most n operations.

If it is possible, print an integer m (0 ≤ m ≤ n), which denotes the number of operations you do.

In each of the next m lines, print three distinct integers i, j, k, representing one operation. 

If there are many such operation sequences possible, print any. Note that you do not have to minimize the number of operations.

Examples

Input


5
4 2 1 7 2


Output


YES
1
1 3 4

Input


4
10 4 49 22


Output


NO

Note

In the first example, the array becomes [4 ⊕ 1 ⊕ 7, 2, 4 ⊕ 1 ⊕ 7, 4 ⊕ 1 ⊕ 7, 2] = [2, 2, 2, 2, 2].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the difference between two collections. The difference means that either the character is present in one collection or it is present in other, but not in both. Return a sorted set with difference.

The collections can contain any character and can contain duplicates.

For instance:

A = [a,a,t,e,f,i,j]

B = [t,g,g,i,k,f]

difference = [a,e,g,j,k]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of strings.
A move onto S consists of swapping any two even indexed characters of S, or any two odd indexed characters of S.
Two strings S and T are special-equivalent if after any number of moves onto S, S == T.
For example, S = "zzxy" and T = "xyzz" are special-equivalent because we may make the moves "zzxy" -> "xzzy" -> "xyzz" that swap S[0] and S[2], then S[1] and S[3].
Now, a group of special-equivalent strings from A is a non-empty subset of A such that:

Every pair of strings in the group are special equivalent, and;
The group is the largest size possible (ie., there isn't a string S not in the group such that S is special equivalent to every string in the group)

Return the number of groups of special-equivalent strings from A.
 

Example 1:
Input: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3
Explanation: 
One group is ["abcd", "cdab", "cbad"], since they are all pairwise special equivalent, and none of the other strings are all pairwise special equivalent to these.

The other two groups are ["xyzz", "zzxy"] and ["zzyx"].  Note that in particular, "zzxy" is not special equivalent to "zzyx".


Example 2:
Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
 






Note:

1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i] consist of only lowercase letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n positive integers written on the blackboard. Also, a positive number k ≥ 2 is chosen, and none of the numbers on the blackboard are divisible by k. In one operation, you can choose any two integers x and y, erase them and write one extra number f(x + y), where f(x) is equal to x if x is not divisible by k, otherwise f(x) = f(x / k).

In the end, there will be a single number of the blackboard. Is it possible to make the final number equal to 1? If so, restore any sequence of operations to do so.

Input

The first line contains two integers n and k — the initial number of integers on the blackboard, and the chosen number (2 ≤ n ≤ 16, 2 ≤ k ≤ 2000).

The second line contains n positive integers a_1, …, a_n initially written on the blackboard. It is guaranteed that none of the numbers a_i is divisible by k, and the sum of all a_i does not exceed 2000.

Output

If it is impossible to obtain 1 as the final number, print "NO" in the only line.

Otherwise, print "YES" on the first line, followed by n - 1 lines describing operations. The i-th of these lines has to contain two integers x_i and y_i to be erased and replaced with f(x_i + y_i) on the i-th operation. If there are several suitable ways, output any of them.

Examples

Input


2 2
1 1


Output


YES
1 1


Input


4 3
7 8 13 23


Output


YES
23 13
8 7
5 4


Input


3 4
1 2 3


Output


NO

Note

In the second sample case:

  * f(8 + 7) = f(15) = f(5) = 5;
  * f(23 + 13) = f(36) = f(12) = f(4) = 4;
  * f(5 + 4) = f(9) = f(3) = f(1) = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Seating On Bus

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Consider 2*n* rows of the seats in a bus. *n* rows of the seats on the left and *n* rows of the seats on the right. Each row can be filled by two people. So the total capacity of the bus is 4*n*.

Consider that *m* (*m*<=≤<=4*n*) people occupy the seats in the bus. The passengers entering the bus are numbered from 1 to *m* (in the order of their entering the bus). The pattern of the seat occupation is as below:

1-st row left window seat, 1-st row right window seat, 2-nd row left window seat, 2-nd row right window seat, ... , *n*-th row left window seat, *n*-th row right window seat.

After occupying all the window seats (for *m*<=&gt;<=2*n*) the non-window seats are occupied:

1-st row left non-window seat, 1-st row right non-window seat, ... , *n*-th row left non-window seat, *n*-th row right non-window seat.

All the passengers go to a single final destination. In the final destination, the passengers get off in the given order.

1-st row left non-window seat, 1-st row left window seat, 1-st row right non-window seat, 1-st row right window seat, ... , *n*-th row left non-window seat, *n*-th row left window seat, *n*-th row right non-window seat, *n*-th row right window seat.

You are given the values *n* and *m*. Output *m* numbers from 1 to *m*, the order in which the passengers will get off the bus.

Input Specification:
The only line contains two integers, *n* and *m* (1<=≤<=*n*<=≤<=100,<=1<=≤<=*m*<=≤<=4*n*) — the number of pairs of rows and the number of passengers.

Output Specification:
Print *m* distinct integers from 1 to *m* — the order in which the passengers will get off the bus.

Demo Input:
['2 7\n', '9 36\n']

Demo Output:
['5 1 6 2 7 3 4\n', '19 1 20 2 21 3 22 4 23 5 24 6 25 7 26 8 27 9 28 10 29 11 30 12 31 13 32 14 33 15 34 16 35 17 36 18\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dreamoon has a string *s* and a pattern string *p*. He first removes exactly *x* characters from *s* obtaining string *s*' as a result. Then he calculates  that is defined as the maximal number of non-overlapping substrings equal to *p* that can be found in *s*'. He wants to make this number as big as possible.

More formally, let's define  as maximum value of  over all *s*' that can be obtained by removing exactly *x* characters from *s*. Dreamoon wants to know  for all *x* from 0 to |*s*| where |*s*| denotes the length of string *s*.

Input Specification:
The first line of the input contains the string *s* (1<=≤<=|*s*|<=≤<=2<=000).

The second line of the input contains the string *p* (1<=≤<=|*p*|<=≤<=500).

Both strings will only consist of lower case English letters.

Output Specification:
Print |*s*|<=+<=1 space-separated integers in a single line representing the  for all *x* from 0 to |*s*|.

Demo Input:
['aaaaa\naa\n', 'axbaxxb\nab\n']

Demo Output:
['2 2 1 1 0 0\n', '0 1 1 2 1 1 0 0\n']

Note:
For the first sample, the corresponding optimal values of *s*' after removal 0 through |*s*| = 5 characters from *s* are {"aaaaa", "aaaa", "aaa", "aa", "a", ""}. 

For the second sample, possible corresponding optimal values of *s*' are {"axbaxxb", "abaxxb", "axbab", "abab", "aba", "ab", "a", ""}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a set of dominoes. Each domino is a rectangular tile with a line dividing its face into two square ends. Can you put all dominoes in a line one by one from left to right so that any two dominoes touched with the sides that had the same number of points? You can rotate the dominoes, changing the left and the right side (domino "1-4" turns into "4-1").

Input

The first line contains number n (1 ≤ n ≤ 100). Next n lines contains the dominoes. Each of these lines contains two numbers — the number of points (spots) on the left and the right half, correspondingly. The numbers of points (spots) are non-negative integers from 0 to 6.

Output

Print "No solution", if it is impossible to arrange the dominoes in the required manner. If the solution exists, then describe any way to arrange the dominoes. You put the dominoes from left to right. In each of n lines print the index of the domino to put in the corresponding position and then, after a space, character "+" (if you don't need to turn the domino) or "–" (if you need to turn it).

Examples

Input

5
1 2
2 4
2 4
6 4
2 1


Output

2 -
1 -
5 -
3 +
4 -

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