meetforever/GRPO_CL huggingface dataset:
user: Ramesses knows a lot about problems involving trees (undirected connected graphs without cycles)!

He created a new useful tree decomposition, but he does not know how to construct it, so he asked you for help!

The decomposition is the splitting the edges of the tree in some simple paths in such a way that each two paths have at least one common vertex. Each edge of the tree should be in exactly one path.

Help Remesses, find such a decomposition of the tree or derermine that there is no such decomposition.


-----Input-----

The first line contains a single integer $n$ ($2 \leq n \leq 10^{5}$) the number of nodes in the tree.

Each of the next $n - 1$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — the edges of the tree. It is guaranteed that the given edges form a tree.


-----Output-----

If there are no decompositions, print the only line containing "No".

Otherwise in the first line print "Yes", and in the second line print the number of paths in the decomposition $m$. 

Each of the next $m$ lines should contain two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$) denoting that one of the paths in the decomposition is the simple path between nodes $u_i$ and $v_i$. 

Each pair of paths in the decomposition should have at least one common vertex, and each edge of the tree should be presented in exactly one path. You can print the paths and the ends of each path in arbitrary order.

If there are multiple decompositions, print any.


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

Output
Yes
1
1 4

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

Output
No

Input
5
1 2
1 3
1 4
1 5

Output
Yes
4
1 2
1 3
1 4
1 5



-----Note-----

The tree from the first example is shown on the picture below: [Image] The number next to each edge corresponds to the path number in the decomposition. It is easy to see that this decomposition suits the required conditions.

The tree from the second example is shown on the picture below: [Image] We can show that there are no valid decompositions of this tree.

The tree from the third example is shown on the picture below: [Image] The number next to each edge corresponds to the path number in the decomposition. It is easy to see that this decomposition suits the required conditions.
user: Polycarp has just attempted to pass the driving test. He ran over the straight road with the signs of four types.

  speed limit: this sign comes with a positive integer number — maximal speed of the car after the sign (cancel the action of the previous sign of this type);  overtake is allowed: this sign means that after some car meets it, it can overtake any other car;  no speed limit: this sign cancels speed limit if any (car can move with arbitrary speed after this sign);  no overtake allowed: some car can't overtake any other car after this sign. 

Polycarp goes past the signs consequentially, each new sign cancels the action of all the previous signs of it's kind (speed limit/overtake). It is possible that two or more "no overtake allowed" signs go one after another with zero "overtake is allowed" signs between them. It works with "no speed limit" and "overtake is allowed" signs as well.

In the beginning of the ride overtake is allowed and there is no speed limit.

You are given the sequence of events in chronological order — events which happened to Polycarp during the ride. There are events of following types:

  Polycarp changes the speed of his car to specified (this event comes with a positive integer number);  Polycarp's car overtakes the other car;  Polycarp's car goes past the "speed limit" sign (this sign comes with a positive integer);  Polycarp's car goes past the "overtake is allowed" sign;  Polycarp's car goes past the "no speed limit";  Polycarp's car goes past the "no overtake allowed"; 

It is guaranteed that the first event in chronological order is the event of type 1 (Polycarp changed the speed of his car to specified).

After the exam Polycarp can justify his rule violations by telling the driving instructor that he just didn't notice some of the signs. What is the minimal number of signs Polycarp should say he didn't notice, so that he would make no rule violations from his point of view?


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 2·10^5) — number of events.

Each of the next n lines starts with integer t (1 ≤ t ≤ 6) — the type of the event.

An integer s (1 ≤ s ≤ 300) follows in the query of the first and the third type (if it is the query of first type, then it's new speed of Polycarp's car, if it is the query of third type, then it's new speed limit).

It is guaranteed that the first event in chronological order is the event of type 1 (Polycarp changed the speed of his car to specified).


-----Output-----

Print the minimal number of road signs Polycarp should say he didn't notice, so that he would make no rule violations from his point of view.


-----Examples-----
Input
11
1 100
3 70
4
2
3 120
5
3 120
6
1 150
4
3 300

Output
2

Input
5
1 100
3 200
2
4
5

Output
0

Input
7
1 20
2
6
4
6
6
2

Output
2



-----Note-----

In the first example Polycarp should say he didn't notice the "speed limit" sign with the limit of 70 and the second "speed limit" sign with the limit of 120.

In the second example Polycarp didn't make any rule violation.

In the third example Polycarp should say he didn't notice both "no overtake allowed" that came after "overtake is allowed" sign.
user: Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph.

There are n vertices in the tree, each of them is painted black or white. Anton doesn't like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white).

To change the colors Anton can use only operations of one type. We denote it as paint(v), where v is some vertex of the tree. This operation changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color (including v and u). For example, consider the tree [Image] 

and apply operation paint(3) to get the following: [Image] 

Anton is interested in the minimum number of operation he needs to perform in order to make the colors of all vertices equal.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n integers color_{i} (0 ≤ color_{i} ≤ 1) — colors of the vertices. color_{i} = 0 means that the i-th vertex is initially painted white, while color_{i} = 1 means it's initially painted black.

Then follow n - 1 line, each of them contains a pair of integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — indices of vertices connected by the corresponding edge. It's guaranteed that all pairs (u_{i}, v_{i}) are distinct, i.e. there are no multiple edges.


-----Output-----

Print one integer — the minimum number of operations Anton has to apply in order to make all vertices of the tree black or all vertices of the tree white.


-----Examples-----
Input
11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11

Output
2

Input
4
0 0 0 0
1 2
2 3
3 4

Output
0



-----Note-----

In the first sample, the tree is the same as on the picture. If we first apply operation paint(3) and then apply paint(6), the tree will become completely black, so the answer is 2.

In the second sample, the tree is already white, so there is no need to apply any operations and the answer is 0.
user: Marcin is a coach in his university. There are $n$ students who want to attend a training camp. Marcin is a smart coach, so he wants to send only the students that can work calmly with each other.

Let's focus on the students. They are indexed with integers from $1$ to $n$. Each of them can be described with two integers $a_i$ and $b_i$; $b_i$ is equal to the skill level of the $i$-th student (the higher, the better). Also, there are $60$ known algorithms, which are numbered with integers from $0$ to $59$. If the $i$-th student knows the $j$-th algorithm, then the $j$-th bit ($2^j$) is set in the binary representation of $a_i$. Otherwise, this bit is not set.

Student $x$ thinks that he is better than student $y$ if and only if $x$ knows some algorithm which $y$ doesn't know. Note that two students can think that they are better than each other. A group of students can work together calmly if no student in this group thinks that he is better than everyone else in this group.

Marcin wants to send a group of at least two students which will work together calmly and will have the maximum possible sum of the skill levels. What is this sum?


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 7000$) — the number of students interested in the camp.

The second line contains $n$ integers. The $i$-th of them is $a_i$ ($0 \leq a_i < 2^{60}$).

The third line contains $n$ integers. The $i$-th of them is $b_i$ ($1 \leq b_i \leq 10^9$).


-----Output-----

Output one integer which denotes the maximum sum of $b_i$ over the students in a group of students which can work together calmly. If no group of at least two students can work together calmly, print 0.


-----Examples-----
Input
4
3 2 3 6
2 8 5 10

Output
15

Input
3
1 2 3
1 2 3

Output
0

Input
1
0
1

Output
0



-----Note-----

In the first sample test, it's optimal to send the first, the second and the third student to the camp. It's also possible to send only the first and the third student, but they'd have a lower sum of $b_i$.

In the second test, in each group of at least two students someone will always think that he is better than everyone else in the subset.
user: They say "years are like dominoes, tumbling one after the other". But would a year fit into a grid? I don't think so.

Limak is a little polar bear who loves to play. He has recently got a rectangular grid with h rows and w columns. Each cell is a square, either empty (denoted by '.') or forbidden (denoted by '#'). Rows are numbered 1 through h from top to bottom. Columns are numbered 1 through w from left to right.

Also, Limak has a single domino. He wants to put it somewhere in a grid. A domino will occupy exactly two adjacent cells, located either in one row or in one column. Both adjacent cells must be empty and must be inside a grid.

Limak needs more fun and thus he is going to consider some queries. In each query he chooses some rectangle and wonders, how many way are there to put a single domino inside of the chosen rectangle?


-----Input-----

The first line of the input contains two integers h and w (1 ≤ h, w ≤ 500) – the number of rows and the number of columns, respectively.

The next h lines describe a grid. Each line contains a string of the length w. Each character is either '.' or '#' — denoting an empty or forbidden cell, respectively.

The next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of queries.

Each of the next q lines contains four integers r1_{i}, c1_{i}, r2_{i}, c2_{i} (1 ≤ r1_{i} ≤ r2_{i} ≤ h, 1 ≤ c1_{i} ≤ c2_{i} ≤ w) — the i-th query. Numbers r1_{i} and c1_{i} denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers r2_{i} and c2_{i} denote the row and the column (respectively) of the bottom right cell of the rectangle.


-----Output-----

Print q integers, i-th should be equal to the number of ways to put a single domino inside the i-th rectangle.


-----Examples-----
Input
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8

Output
4
0
10
15

Input
7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8

Output
53
89
120
23
0
2



-----Note-----

A red frame below corresponds to the first query of the first sample. A domino can be placed in 4 possible ways. [Image]
user: Pink Floyd are pulling a prank on Roger Waters. They know he doesn't like walls, he wants to be able to walk freely, so they are blocking him from exiting his room which can be seen as a grid.

Roger Waters has a square grid of size $n\times n$ and he wants to traverse his grid from the upper left ($1,1$) corner to the lower right corner ($n,n$). Waters can move from a square to any other square adjacent by a side, as long as he is still in the grid. Also except for the cells ($1,1$) and ($n,n$) every cell has a value $0$ or $1$ in it.

Before starting his traversal he will pick either a $0$ or a $1$ and will be able to only go to cells values in which are equal to the digit he chose. The starting and finishing cells ($1,1$) and ($n,n$) are exempt from this rule, he may go through them regardless of picked digit. Because of this the cell ($1,1$) takes value the letter 'S' and the cell ($n,n$) takes value the letter 'F'.

For example, in the first example test case, he can go from ($1, 1$) to ($n, n$) by using the zeroes on this path: ($1, 1$), ($2, 1$), ($2, 2$), ($2, 3$), ($3, 3$), ($3, 4$), ($4, 4$)

The rest of the band (Pink Floyd) wants Waters to not be able to do his traversal, so while he is not looking they will invert at most two cells in the grid (from $0$ to $1$ or vice versa). They are afraid they will not be quick enough and asked for your help in choosing the cells.  Note that you cannot invert cells $(1, 1)$ and $(n, n)$.

We can show that there always exists a solution for the given constraints.

Also note that Waters will pick his digit of the traversal after the band has changed his grid, so he must not be able to reach ($n,n$) no matter what digit he picks.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$). Description of the test cases follows.

The first line of each test case contains one integers $n$ ($3 \le n \le 200$).

The following $n$ lines of each test case contain the binary grid, square ($1, 1$) being colored in 'S' and square ($n, n$) being colored in 'F'.

The sum of values of $n$ doesn't exceed $200$.


-----Output-----

For each test case output on the first line an integer $c$ ($0 \le c \le 2$)  — the number of inverted cells.

In $i$-th of the following $c$ lines, print the coordinates of the $i$-th cell you inverted. You may not invert the same cell twice.  Note that you cannot invert cells $(1, 1)$ and $(n, n)$.


-----Example-----
Input
3
4
S010
0001
1000
111F
3
S10
101
01F
5
S0101
00000
01111
11111
0001F

Output
1
3 4
2
1 2
2 1
0



-----Note-----

For the first test case, after inverting the cell, we get the following grid:



S010

0001

1001

111F
user: Ghosts live in harmony and peace, they travel the space without any purpose other than scare whoever stands in their way.

There are $n$ ghosts in the universe, they move in the $OXY$ plane, each one of them has its own velocity that does not change in time: $\overrightarrow{V} = V_{x}\overrightarrow{i} + V_{y}\overrightarrow{j}$ where $V_{x}$ is its speed on the $x$-axis and $V_{y}$ is on the $y$-axis.

A ghost $i$ has experience value $EX_i$, which represent how many ghosts tried to scare him in his past. Two ghosts scare each other if they were in the same cartesian point at a moment of time.

As the ghosts move with constant speed, after some moment of time there will be no further scaring (what a relief!) and the experience of ghost kind $GX = \sum_{i=1}^{n} EX_i$ will never increase.

Tameem is a red giant, he took a picture of the cartesian plane at a certain moment of time $T$, and magically all the ghosts were aligned on a line of the form $y = a \cdot x + b$. You have to compute what will be the experience index of the ghost kind $GX$ in the indefinite future, this is your task for today.

Note that when Tameem took the picture, $GX$ may already be greater than $0$, because many ghosts may have scared one another at any moment between $[-\infty, T]$.


-----Input-----

The first line contains three integers $n$, $a$ and $b$ ($1 \leq n \leq 200000$, $1 \leq |a| \leq 10^9$, $0 \le |b| \le 10^9$) — the number of ghosts in the universe and the parameters of the straight line.

Each of the next $n$ lines contains three integers $x_i$, $V_{xi}$, $V_{yi}$ ($-10^9 \leq x_i \leq 10^9$, $-10^9 \leq V_{x i}, V_{y i} \leq 10^9$), where $x_i$ is the current $x$-coordinate of the $i$-th ghost (and $y_i = a \cdot x_i + b$).

It is guaranteed that no two ghosts share the same initial position, in other words, it is guaranteed that for all $(i,j)$ $x_i \neq x_j$ for $i \ne j$.


-----Output-----

Output one line: experience index of the ghost kind $GX$ in the indefinite future.


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

Output
8

Input
3 1 0
-1 1 0
0 0 -1
1 -1 -2

Output
6

Input
3 1 0
0 0 0
1 0 0
2 0 0

Output
0



-----Note-----

There are four collisions $(1,2,T-0.5)$, $(1,3,T-1)$, $(2,4,T+1)$, $(3,4,T+0.5)$, where $(u,v,t)$ means a collision happened between ghosts $u$ and $v$ at moment $t$. At each collision, each ghost gained one experience point, this means that $GX = 4 \cdot 2 = 8$.

In the second test, all points will collide when $t = T + 1$.  [Image] 

The red arrow represents the 1-st ghost velocity, orange represents the 2-nd ghost velocity, and blue represents the 3-rd ghost velocity.
user: You are given a sequence of n positive integers d_1, d_2, ..., d_{n} (d_1 < d_2 < ... < d_{n}). Your task is to construct an undirected graph such that:

  there are exactly d_{n} + 1 vertices;  there are no self-loops;  there are no multiple edges;  there are no more than 10^6 edges;  its degree set is equal to d. 

Vertices should be numbered 1 through (d_{n} + 1).

Degree sequence is an array a with length equal to the number of vertices in a graph such that a_{i} is the number of vertices adjacent to i-th vertex.

Degree set is a sorted in increasing order sequence of all distinct values from the degree sequence.

It is guaranteed that there exists such a graph that all the conditions hold, and it contains no more than 10^6 edges.

Print the resulting graph.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 300) — the size of the degree set.

The second line contains n integers d_1, d_2, ..., d_{n} (1 ≤ d_{i} ≤ 1000, d_1 < d_2 < ... < d_{n}) — the degree set.


-----Output-----

In the first line print one integer m (1 ≤ m ≤ 10^6) — the number of edges in the resulting graph. It is guaranteed that there exists such a graph that all the conditions hold and it contains no more than 10^6 edges.

Each of the next m lines should contain two integers v_{i} and u_{i} (1 ≤ v_{i}, u_{i} ≤ d_{n} + 1) — the description of the i-th edge.


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

Output
8
3 1
4 2
4 5
2 5
5 1
3 2
2 1
5 3

Input
3
1 2 3

Output
4
1 2
1 3
1 4
2 3
user: The bear has a string s = s_1s_2... s_{|}s| (record |s| is the string's length), consisting of lowercase English letters. The bear wants to count the number of such pairs of indices i, j (1 ≤ i ≤ j ≤ |s|), that string x(i, j) = s_{i}s_{i} + 1... s_{j} contains at least one string "bear" as a substring.

String x(i, j) contains string "bear", if there is such index k (i ≤ k ≤ j - 3), that s_{k} = b, s_{k} + 1 = e, s_{k} + 2 = a, s_{k} + 3 = r.

Help the bear cope with the given problem.


-----Input-----

The first line contains a non-empty string s (1 ≤ |s| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters.


-----Output-----

Print a single number — the answer to the problem.


-----Examples-----
Input
bearbtear

Output
6

Input
bearaabearc

Output
20



-----Note-----

In the first sample, the following pairs (i, j) match: (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9).

In the second sample, the following pairs (i, j) match: (1,  4), (1,  5), (1,  6), (1,  7), (1,  8), (1,  9), (1,  10), (1,  11), (2,  10), (2,  11), (3,  10), (3,  11), (4,  10), (4,  11), (5,  10), (5,  11), (6,  10), (6,  11), (7,  10), (7,  11).
user: Pasha got a very beautiful string s for his birthday, the string consists of lowercase Latin letters. The letters in the string are numbered from 1 to |s| from left to right, where |s| is the length of the given string.

Pasha didn't like his present very much so he decided to change it. After his birthday Pasha spent m days performing the following transformations on his string — each day he chose integer a_{i} and reversed a piece of string (a segment) from position a_{i} to position |s| - a_{i} + 1. It is guaranteed that 2·a_{i} ≤ |s|.

You face the following task: determine what Pasha's string will look like after m days.


-----Input-----

The first line of the input contains Pasha's string s of length from 2 to 2·10^5 characters, consisting of lowercase Latin letters.

The second line contains a single integer m (1 ≤ m ≤ 10^5) —  the number of days when Pasha changed his string.

The third line contains m space-separated elements a_{i} (1 ≤ a_{i}; 2·a_{i} ≤ |s|) — the position from which Pasha started transforming the string on the i-th day.


-----Output-----

In the first line of the output print what Pasha's string s will look like after m days.


-----Examples-----
Input
abcdef
1
2

Output
aedcbf

Input
vwxyz
2
2 2

Output
vwxyz

Input
abcdef
3
1 2 3

Output
fbdcea
user: You are given a chess board with $n$ rows and $n$ columns. Initially all cells of the board are empty, and you have to put a white or a black knight into each cell of the board.

A knight is a chess piece that can attack a piece in cell ($x_2$, $y_2$) from the cell ($x_1$, $y_1$) if one of the following conditions is met:

  $|x_1 - x_2| = 2$ and $|y_1 - y_2| = 1$, or  $|x_1 - x_2| = 1$ and $|y_1 - y_2| = 2$. 

Here are some examples of which cells knight can attack. In each of the following pictures, if the knight is currently in the blue cell, it can attack all red cells (and only them).

 [Image] 

A duel of knights is a pair of knights of different colors such that these knights attack each other. You have to put a knight (a white one or a black one) into each cell in such a way that the number of duels is maximum possible.


-----Input-----

The first line contains one integer $n$ ($3 \le n \le 100$) — the number of rows (and columns) in the board.


-----Output-----

Print $n$ lines with $n$ characters in each line. The $j$-th character in the $i$-th line should be W, if the cell ($i$, $j$) contains a white knight, or B, if it contains a black knight. The number of duels should be maximum possible. If there are multiple optimal answers, print any of them.


-----Example-----
Input
3

Output
WBW
BBB
WBW



-----Note-----

In the first example, there are $8$ duels:

  the white knight in ($1$, $1$) attacks the black knight in ($3$, $2$);  the white knight in ($1$, $1$) attacks the black knight in ($2$, $3$);  the white knight in ($1$, $3$) attacks the black knight in ($3$, $2$);  the white knight in ($1$, $3$) attacks the black knight in ($2$, $1$);  the white knight in ($3$, $1$) attacks the black knight in ($1$, $2$);  the white knight in ($3$, $1$) attacks the black knight in ($2$, $3$);  the white knight in ($3$, $3$) attacks the black knight in ($1$, $2$);  the white knight in ($3$, $3$) attacks the black knight in ($2$, $1$).