vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In the house where Krosh used to live, he had n cupboards standing in a line, the i-th cupboard had the height of h_i. Krosh moved recently, but he wasn't able to move the cupboards with him. Now he wants to buy n new cupboards so that they look as similar to old ones as possible.

Krosh does not remember the exact heights of the cupboards, but for every three consecutive cupboards he remembers the height difference between the tallest and the shortest of them. In other words, if the cupboards' heights were h_1, h_2, …, h_n, then Krosh remembers the values w_i = max(h_{i}, h_{i + 1}, h_{i + 2}) - min(h_{i}, h_{i + 1}, h_{i + 2}) for all 1 ≤ i ≤ n - 2.

Krosh wants to buy such n cupboards that all the values w_i remain the same. Help him determine the required cupboards' heights, or determine that he remembers something incorrectly and there is no suitable sequence of heights.

Input

The first line contains two integers n and C (3 ≤ n ≤ 10^6, 0 ≤ C ≤ 10^{12}) — the number of cupboards and the limit on possible w_i.

The second line contains n - 2 integers w_1, w_2, …, w_{n - 2} (0 ≤ w_i ≤ C) — the values defined in the statement.

Output

If there is no suitable sequence of n cupboards, print "NO".

Otherwise print "YES" in the first line, then in the second line print n integers h'_1, h'_2, …, h'_n (0 ≤ h'_i ≤ 10^{18}) — the heights of the cupboards to buy, from left to right.

We can show that if there is a solution, there is also a solution satisfying the constraints on heights.

If there are multiple answers, print any.

Examples

Input


7 20
4 8 12 16 20


Output


YES
4 8 8 16 20 4 0 


Input


11 10
5 7 2 3 4 5 2 1 8


Output


YES
1 1 6 8 6 5 2 0 0 1 8 


Input


6 9
1 6 9 0


Output


NO

Note

Consider the first example:

  * w_1 = max(4, 8, 8) - min(4, 8, 8) = 8 - 4 = 4 
  * w_2 = max(8, 8, 16) - min(8, 8, 16) = 16 - 8 = 8 
  * w_3 = max(8, 16, 20) - min(8, 16, 20) = 20 - 8 = 12 
  * w_4 = max(16, 20, 4) - min(16, 20, 4) = 20 - 4 = 16 
  * w_5 = max(20, 4, 0) - min(20, 4, 0) = 20 - 0 = 20 



There are other possible solutions, for example, the following: 0, 1, 4, 9, 16, 25, 36.

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 through N.
The i-th edge connects Vertex x_i and y_i.
Each vertex is painted white or black.
The initial color of Vertex i is represented by a letter c_i.
c_i = W represents the vertex is white; c_i = B represents the vertex is black.
A cat will walk along this tree.
More specifically, she performs one of the following in one second repeatedly:
 - Choose a vertex that is adjacent to the vertex where she is currently, and move to that vertex. Then, invert the color of the destination vertex.
 - Invert the color of the vertex where she is currently.
The cat's objective is to paint all the vertices black. She may start and end performing actions at any vertex.
At least how many seconds does it takes for the cat to achieve her objective?

-----Constraints-----
 - 1 ≤ N ≤ 10^5
 - 1 ≤ x_i,y_i ≤ N (1 ≤ i ≤ N-1)
 - The given graph is a tree.
 - c_i = W or c_i = B.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}
c_1c_2..c_N

-----Output-----
Print the minimum number of seconds required to achieve the objective.

-----Sample Input-----
5
1 2
2 3
2 4
4 5
WBBWW

-----Sample Output-----
5

The objective can be achieved in five seconds, for example, as follows:
 - Start at Vertex 1. Change the color of Vertex 1 to black.
 - Move to Vertex 2, then change the color of Vertex 2 to white.
 - Change the color of Vertex 2 to black.
 - Move to Vertex 4, then change the color of Vertex 4 to black.
 - Move to Vertex 5, then change the color of Vertex 5 to black.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a cave.
The cave has N rooms and M passages. The rooms are numbered 1 to N, and the passages are numbered 1 to M. Passage i connects Room A_i and Room B_i bidirectionally. One can travel between any two rooms by traversing passages. Room 1 is a special room with an entrance from the outside.
It is dark in the cave, so we have decided to place a signpost in each room except Room 1. The signpost in each room will point to one of the rooms directly connected to that room with a passage.
Since it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room 1.
 - If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room 1 after traversing the minimum number of passages possible.
Determine whether there is a way to place signposts satisfying our objective, and print one such way if it exists.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - 1 \leq M \leq 2 \times 10^5
 - 1 \leq A_i, B_i \leq N\ (1 \leq i \leq M)
 - A_i \neq B_i\ (1 \leq i \leq M)
 - One can travel between any two rooms by traversing passages.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1
:
A_M B_M

-----Output-----
If there is no way to place signposts satisfying the objective, print No.
Otherwise, print N lines. The first line should contain Yes, and the i-th line (2 \leq i \leq N) should contain the integer representing the room indicated by the signpost in Room i.

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

-----Sample Output-----
Yes
1
2
2

If we place the signposts as described in the sample output, the following happens:
 - Starting in Room 2, you will reach Room 1 after traversing one passage: (2) \to 1. This is the minimum number of passages possible.
 - Starting in Room 3, you will reach Room 1 after traversing two passages: (3) \to 2 \to 1. This is the minimum number of passages possible.
 - Starting in Room 4, you will reach Room 1 after traversing two passages: (4) \to 2 \to 1. This is the minimum number of passages possible.
Thus, the objective is satisfied.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the length between 2 co-ordinates.  The co-ordinates are made of integers between -20 and 20 and will be given in the form of a 2D array:

(0,0) and (5,-7) would be [ [ 0 , 0 ] , [ 5, -7 ] ]

The function must return the answer rounded to 2 decimal places in the form of a string.

```python
length_of_line([[0, 0], [5, -7]]) => "8.60"
```

If the 2 given co-ordinates are the same, the returned length should be "0.00"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Theater stage is a rectangular field of size n × m. The director gave you the stage's plan which actors will follow. For each cell it is stated in the plan if there would be an actor in this cell or not.

You are to place a spotlight on the stage in some good position. The spotlight will project light in one of the four directions (if you look at the stage from above) — left, right, up or down. Thus, the spotlight's position is a cell it is placed to and a direction it shines.

A position is good if two conditions hold:   there is no actor in the cell the spotlight is placed to;  there is at least one actor in the direction the spotlight projects. 

Count the number of good positions for placing the spotlight. Two positions of spotlight are considered to be different if the location cells or projection direction differ.


-----Input-----

The first line contains two positive integers n and m (1 ≤ n, m ≤ 1000) — the number of rows and the number of columns in the plan.

The next n lines contain m integers, 0 or 1 each — the description of the plan. Integer 1, means there will be an actor in the corresponding cell, while 0 means the cell will remain empty. It is guaranteed that there is at least one actor in the plan.


-----Output-----

Print one integer — the number of good positions for placing the spotlight.


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

Output
9

Input
4 4
0 0 0 0
1 0 0 1
0 1 1 0
0 1 0 0

Output
20



-----Note-----

In the first example the following positions are good:  the (1, 1) cell and right direction;  the (1, 1) cell and down direction;  the (1, 3) cell and left direction;  the (1, 3) cell and down direction;  the (1, 4) cell and left direction;  the (2, 2) cell and left direction;  the (2, 2) cell and up direction;  the (2, 2) and right direction;  the (2, 4) cell and left direction. 

Therefore, there are 9 good positions in this example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once upon a time, a CodeWarrior, after reading a [discussion on what can be the plural](http://www.codewars.com/kata/plural/discuss/javascript), took a look at [this page](http://en.wikipedia.org/wiki/Grammatical_number#Types_of_number
) and discovered that **more than 1** "kind of plural" may exist. 

For example [Sursurunga Language](http://en.wikipedia.org/wiki/Sursurunga_language) distinguishes 5 types of numbers: **singular** (1 thing), **dual** (2 things), '**trial**' or '**lesser paucal**' (3 or 4), '**greater paucal**' (more than 4) and **plural** (many).

In this kata, you'll have to handle only four types of numbers:

- **singular**: 0 or 1 thing
- **dual**: 2 things
- **paucal**: 3 to 9 things
- **plural**: more than 9 things

To add some flavor the **number-marker** will not be added in same places:

- **singular**, no marker : `1 cat`
- **dual**, prefixed "`bu`" : `2 cats -> 2 bucat`
- **paucal**, suffixed "`zo`" : `4 cats -> 4 catzo`
- **plural**, "circumfixed `ga`" : `100 cats -> 100 gacatga`

As you all ("hawk eyes") have seen, the final `s` of english plural **disappears**.

( btw these markers, of course, have absolutely nothing to do with true sursurunga language, we're just talking about "**pig**-sursurunga" with **pig** as **pig** in "**pig latin**" )

## Your Job . . .
. . . if you accept it, will be to write a `sursurungal` function which get a `string` as argument and returns this string with words in it eventually converted to their "pig-sursurunga number type".

If a `number` ( *ie* 1 or more digit ) + a `space` + a `word` ( letters ) are found then the word should be converted.

**Each** group of `number+space+word` found in the string should be evaluated.

### Examples :

You may assume at least 1 `number+space+word` group will be provided.

**Beware** `s` of english plural should be removed, not ending `s` of some singular words ( *eg* "kiss" )

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a method `sayHello`/`say_hello`/`SayHello` that takes as input a name, city, and state to welcome a person. Note that `name` will be an array consisting of one or more values that should be joined together with one space between each, and the length of the `name` array in test cases will vary.

Example:

```python
say_hello(['John', 'Smith'], 'Phoenix', 'Arizona')
```

This example will return the string `Hello, John Smith! Welcome to Phoenix, Arizona!`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N monsters, numbered 1, 2, ..., N.
Initially, the health of Monster i is A_i.
Below, a monster with at least 1 health is called alive.
Until there is only one alive monster, the following is repeated:
 - A random alive monster attacks another random alive monster.
 - As a result, the health of the monster attacked is reduced by the amount equal to the current health of the monster attacking.
Find the minimum possible final health of the last monster alive.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - 1 \leq A_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the minimum possible final health of the last monster alive.

-----Sample Input-----
4
2 10 8 40

-----Sample Output-----
2

When only the first monster keeps on attacking, the final health of the last monster will be 2, which is minimum.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima and Inna are doing so great! At the moment, Inna is sitting on the magic lawn playing with a pink pony. Dima wanted to play too. He brought an n × m chessboard, a very tasty candy and two numbers a and b.

Dima put the chessboard in front of Inna and placed the candy in position (i, j) on the board. The boy said he would give the candy if it reaches one of the corner cells of the board. He's got one more condition. There can only be actions of the following types:

  move the candy from position (x, y) on the board to position (x - a, y - b);  move the candy from position (x, y) on the board to position (x + a, y - b);  move the candy from position (x, y) on the board to position (x - a, y + b);  move the candy from position (x, y) on the board to position (x + a, y + b). 

Naturally, Dima doesn't allow to move the candy beyond the chessboard borders.

Inna and the pony started shifting the candy around the board. They wonder what is the minimum number of allowed actions that they need to perform to move the candy from the initial position (i, j) to one of the chessboard corners. Help them cope with the task! 


-----Input-----

The first line of the input contains six integers n, m, i, j, a, b (1 ≤ n, m ≤ 10^6; 1 ≤ i ≤ n; 1 ≤ j ≤ m; 1 ≤ a, b ≤ 10^6).

You can assume that the chessboard rows are numbered from 1 to n from top to bottom and the columns are numbered from 1 to m from left to right. Position (i, j) in the statement is a chessboard cell on the intersection of the i-th row and the j-th column. You can consider that the corners are: (1, m), (n, 1), (n, m), (1, 1).


-----Output-----

In a single line print a single integer — the minimum number of moves needed to get the candy.

If Inna and the pony cannot get the candy playing by Dima's rules, print on a single line "Poor Inna and pony!" without the quotes.


-----Examples-----
Input
5 7 1 3 2 2

Output
2

Input
5 5 2 3 1 1

Output
Poor Inna and pony!



-----Note-----

Note to sample 1:

Inna and the pony can move the candy to position (1 + 2, 3 + 2) = (3, 5), from there they can move it to positions (3 - 2, 5 + 2) = (1, 7) and (3 + 2, 5 + 2) = (5, 7). These positions correspond to the corner squares of the chess board. Thus, the answer to the test sample equals two.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a string *s* consisting of *n* lowercase Latin letters. You have to type this string using your keyboard.

Initially, you have an empty string. Until you type the whole string, you may perform the following operation:
 -  add a character to the end of the string. 
Besides, at most once you may perform one additional operation: copy the string and append it to itself.

For example, if you have to type string abcabca, you can type it in 7 operations if you type all the characters one by one. However, you can type it in 5 operations if you type the string abc first and then copy it and type the last character.

If you have to type string aaaaaaaaa, the best option is to type 4 characters one by one, then copy the string, and then type the remaining character.

Print the minimum number of operations you need to type the given string.

Input Specification:
The first line of the input containing only one integer number *n* (1<=≤<=*n*<=≤<=100) — the length of the string you have to type. The second line containing the string *s* consisting of *n* lowercase Latin letters.

Output Specification:
Print one integer number — the minimum number of operations you need to type the given string.

Demo Input:
['7\nabcabca\n', '8\nabcdefgh\n']

Demo Output:
['5\n', '8\n']

Note:
The first test described in the problem statement.

In the second test you can only type all the characters one by one.

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

Find the integer from `a` to `b` (included) with the greatest number of divisors. For example:

```
divNum(15, 30)   ==> 24
divNum(1, 2)     ==> 2
divNum(0, 0)     ==> 0
divNum(52, 156)  ==> 120
```

If there are several numbers that have the same (maximum) number of divisors, the smallest among them should be returned. Return the string `"Error"` if `a > b`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: New Year Letter

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Many countries have such a New Year or Christmas tradition as writing a letter to Santa including a wish list for presents. Vasya is an ordinary programmer boy. Like all ordinary boys, he is going to write the letter to Santa on the New Year Eve (we Russians actually expect Santa for the New Year, not for Christmas). 

Vasya has come up with an algorithm he will follow while writing a letter. First he chooses two strings, *s*1 anf *s*2, consisting of uppercase English letters. Then the boy makes string *s**k*, using a recurrent equation *s**n*<==<=*s**n*<=-<=2<=+<=*s**n*<=-<=1, operation '+' means a concatenation (that is, the sequential record) of strings in the given order. Then Vasya writes down string *s**k* on a piece of paper, puts it in the envelope and sends in to Santa. 

Vasya is absolutely sure that Santa will bring him the best present if the resulting string *s**k* has exactly *x* occurrences of substring AC (the short-cut reminds him оf accepted problems). Besides, Vasya decided that string *s*1 should have length *n*, and string *s*2 should have length *m*. Vasya hasn't decided anything else.

At the moment Vasya's got urgent New Year business, so he asks you to choose two strings for him, *s*1 and *s*2 in the required manner. Help Vasya.

Input Specification:
The first line contains four integers *k*,<=*x*,<=*n*,<=*m* (3<=≤<=*k*<=≤<=50; 0<=≤<=*x*<=≤<=109; 1<=≤<=*n*,<=*m*<=≤<=100).

Output Specification:
In the first line print string *s*1, consisting of *n* uppercase English letters. In the second line print string *s*2, consisting of *m* uppercase English letters. If there are multiple valid strings, print any of them.

If the required pair of strings doesn't exist, print "Happy new year!" without the quotes.

Demo Input:
['3 2 2 2\n', '3 3 2 2\n', '3 0 2 2\n', '4 3 2 1\n', '4 2 2 1\n']

Demo Output:
['AC\nAC\n', 'Happy new year!\n', 'AA\nAA\n', 'Happy new year!\n', 'Happy new year!\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For his birthday, Jeffrey received a tree with N vertices, numbered from 1 to N. Disappointed by the fact that there is only one simple path between any two vertices, Jeffrey decided to remedy this by introducing an extra edge in the tree. Note that this may result in a self loop or multiple edge. After introducing an extra edge, Jeffrey wants to know how many pairs of two vertices are ambiguous. Two vertices are ambiguous if there exists more than one simple path between them. Jeffrey has Q queries — he has decided Q possible locations for the extra edge. Please help him find out how many ambiguous pairs there in the tree if he added each of the Q edges to the tree. The tree will revert back to its original state after each query, so queries are mutually independent.

Input: 
The first line of input will contain N. 
The next N - 1  lines of input will each contain a pair of integers a and b, indicating that there is an edge from vertex a to b. 
The next line of input will contain Q. 
The next Q lines of input will each contain a pair of integers u and v, indicating that Jeffrey is considering putting an extra edge between u and v.

Output: 
Output Q lines, the answers to the queries in the same order as given in the input.

Constraints: 
1 ≤ N ≤ 10^5 
1 ≤ Q ≤ 10^5 
1 ≤ a, b ≤ N, a ≠ b 
1 ≤ u, v ≤ N 
It is guaranteed that the given edges in the initial graph will form a tree.

Note: 
A simple path is a sequence of vertices such that all the vertices in the sequence are unique and each adjacent pair in the sequence are connected by an edge. Two simple paths are different if one vertex exists in one path but not the other or one edge exists in one path but not the other.

SAMPLE INPUT
10
1 2
1 3
2 4
1 5
3 6
3 7
6 8
5 9
5 10
5
2 4
1 8
3 9
9 6
4 10

SAMPLE OUTPUT
9
29
35
39
34

Explanation

Here is the tree given in the test case:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I'm the Map, I'm the Map! I'm the MAP!!!

Map

In anticipation of new adventures Boots wanted to do a good deed. After discussion with the Map and Backpack, they decided to gift Dora a connected graph. After a long search, Boots chose t graph's variants, which Dora might like. However fox Swiper wants to spoil his plan.

The Swiper knows, that Dora now is only able to count up to 3, so he has came up with a following idea. He wants to steal some non-empty set of vertices, so that the Dora won't notice the loss. He has decided to steal some non-empty set of vertices, so that after deletion of the stolen vertices and edges adjacent to them, every remaining vertex wouldn't change it's degree modulo 3. The degree of a vertex is the number of edges it is adjacent to. It would've been suspicious to steal all the vertices, so Swiper needs another plan.

Boots are sure, that the crime can not be allowed. However they are afraid, that they won't be able to handle this alone. So Boots decided to ask for your help. Please determine for every graph's variant whether the Swiper can perform the theft or not.

Input

The first line contains a single integer t (1 ≤ t ≤ 100 000) — the number of graph variants.

The first line of each variant contains integers n, m (1 ≤ n ≤ 500 000, 0 ≤ m ≤ 500 000), the number of vertexes and edges in the graph.

Then m lines follow, each containing integers a_i, b_i (1 ≤ a_i, b_i ≤ n), the indices of the vertices connected with a corresponding edge.

It's guaranteed, that the graph is connected and doesn't contain multiple edges or self-loops.

It's guaranteed, that the sum of n over all variants is at most 500 000 and that the sum of m over all variants is at most 500 000.

Descriptions of graph's variants are separated with an empty line.

Output

For each variant:

  * In case the answer exists, print "Yes" and then the answer itself.

The first line should contain an integer c (1 < c < n), the number of vertices the Crook can steal, without Dora noticing the loss. On the next line print c distinct integers, the indices of the graph's vertices in arbitrary order.

  * Otherwise print "No". 



In case there are several correct ways to steal the vertices, print any of them.

Please note, that it's not required to maximize the number of stolen vertices.

Example

Input


3
3 3
1 2
2 3
3 1

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

8 12
1 2
1 3
2 3
1 4
4 5
5 1
3 6
3 7
3 8
6 1
7 1
8 1


Output


No
Yes
3
4 5 6
Yes
3
6 7 8

Note

The picture below shows the third variant from the example test. The set of the vertices the Crook can steal is denoted with bold. 

<image>

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