meetforever/GRPO_CL huggingface dataset:
user: Vasya is an administrator of a public page of organization "Mouse and keyboard" and his everyday duty is to publish news from the world of competitive programming. For each news he also creates a list of hashtags to make searching for a particular topic more comfortable. For the purpose of this problem we define hashtag as a string consisting of lowercase English letters and exactly one symbol '#' located at the beginning of the string. The length of the hashtag is defined as the number of symbols in it without the symbol '#'.

The head administrator of the page told Vasya that hashtags should go in lexicographical order (take a look at the notes section for the definition).

Vasya is lazy so he doesn't want to actually change the order of hashtags in already published news. Instead, he decided to delete some suffixes (consecutive characters at the end of the string) of some of the hashtags. He is allowed to delete any number of characters, even the whole string except for the symbol '#'. Vasya wants to pick such a way to delete suffixes that the total number of deleted symbols is minimum possible. If there are several optimal solutions, he is fine with any of them.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of hashtags being edited now.

Each of the next n lines contains exactly one hashtag of positive length.

It is guaranteed that the total length of all hashtags (i.e. the total length of the string except for characters '#') won't exceed 500 000.


-----Output-----

Print the resulting hashtags in any of the optimal solutions.


-----Examples-----
Input
3
#book
#bigtown
#big

Output
#b
#big
#big

Input
3
#book
#cool
#cold

Output
#book
#co
#cold

Input
4
#car
#cart
#art
#at

Output
#
#
#art
#at

Input
3
#apple
#apple
#fruit

Output
#apple
#apple
#fruit



-----Note-----

Word a_1, a_2, ..., a_{m} of length m is lexicographically not greater than word b_1, b_2, ..., b_{k} of length k, if one of two conditions hold:   at first position i, such that a_{i} ≠ b_{i}, the character a_{i} goes earlier in the alphabet than character b_{i}, i.e. a has smaller character than b in the first position where they differ;  if there is no such position i and m ≤ k, i.e. the first word is a prefix of the second or two words are equal. 

The sequence of words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically not greater than the next word.

For the words consisting of lowercase English letters the lexicographical order coincides with the alphabet word order in the dictionary.

According to the above definition, if a hashtag consisting of one character '#' it is lexicographically not greater than any other valid hashtag. That's why in the third sample we can't keep first two hashtags unchanged and shorten the other two.
user: You are given an integer L. Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.
 - The number of vertices, N, is at most 20. The vertices are given ID numbers from 1 to N.
 - The number of edges, M, is at most 60. Each edge has an integer length between 0 and 10^6 (inclusive).
 - Every edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, 1,2,...,N is one possible topological order of the vertices.
 - There are exactly L different paths from Vertex 1 to Vertex N. The lengths of these paths are all different, and they are integers between 0 and L-1.
Here, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.

-----Constraints-----
 - 2 \leq L \leq 10^6
 - L is an integer.

-----Input-----
Input is given from Standard Input in the following format:
L

-----Output-----
In the first line, print N and M, the number of the vertices and edges in your graph.
In the i-th of the following M lines, print three integers u_i,v_i and w_i, representing the starting vertex, the ending vertex and the length of the i-th edge.
If there are multiple solutions, any of them will be accepted.

-----Sample Input-----
4

-----Sample Output-----
8 10
1 2 0
2 3 0
3 4 0
1 5 0
2 6 0
3 7 0
4 8 0
5 6 1
6 7 1
7 8 1

In the graph represented by the sample output, there are four paths from Vertex 1 to N=8:
 - 1 → 2 → 3 → 4 → 8 with length 0
 - 1 → 2 → 3 → 7 → 8 with length 1
 - 1 → 2 → 6 → 7 → 8 with length 2
 - 1 → 5 → 6 → 7 → 8 with length 3
There are other possible solutions.
user: Snuke has decided to play with a six-sided die. Each of its six sides shows an integer 1 through 6, and two numbers on opposite sides always add up to 7.
Snuke will first put the die on the table with an arbitrary side facing upward, then repeatedly perform the following operation:
 - Operation: Rotate the die 90° toward one of the following directions: left, right, front (the die will come closer) and back (the die will go farther). Then, obtain y points where y is the number written in the side facing upward.
For example, let us consider the situation where the side showing 1 faces upward, the near side shows 5 and the right side shows 4, as illustrated in the figure.
If the die is rotated toward the right as shown in the figure, the side showing 3 will face upward.
Besides, the side showing 4 will face upward if the die is rotated toward the left, the side showing 2 will face upward if the die is rotated toward the front, and the side showing 5 will face upward if the die is rotated toward the back.
Find the minimum number of operation Snuke needs to perform in order to score at least x points in total.

-----Constraints-----
 - 1 ≦ x ≦ 10^{15}
 - x is an integer.

-----Input-----
The input is given from Standard Input in the following format:
x

-----Output-----
Print the answer.

-----Sample Input-----
7

-----Sample Output-----
2
user: We have a tree with N vertices numbered 1 to N.
The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i.
Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:
 - For any two vertices painted in the same color, the distance between them is an even number.
Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^5
 - 1 \leq u_i < v_i \leq N
 - 1 \leq w_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
u_1 v_1 w_1
u_2 v_2 w_2
.
.
.
u_{N - 1} v_{N - 1} w_{N - 1}

-----Output-----
Print a coloring of the vertices that satisfies the condition, in N lines.
The i-th line should contain 0 if Vertex i is painted white and 1 if it is painted black.
If there are multiple colorings that satisfy the condition, any of them will be accepted.

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

-----Sample Output-----
0
0
1
user: We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:
 - For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.
 - There is an edge between Vertex X and Vertex Y.
For each k=1,2,...,N-1, solve the problem below:
 - Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

-----Constraints-----
 - 3 \leq N \leq 2 \times 10^3
 - 1 \leq X,Y \leq N
 - X+1 < Y
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N X Y

-----Output-----
For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

-----Sample Input-----
5 2 4

-----Sample Output-----
5
4
1
0

The graph in this input is as follows:





There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).


There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).


There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).


There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.
user: During the lunch break all n Berland State University students lined up in the food court. However, it turned out that the food court, too, has a lunch break and it temporarily stopped working.

Standing in a queue that isn't being served is so boring! So, each of the students wrote down the number of the student ID of the student that stands in line directly in front of him, and the student that stands in line directly behind him. If no one stands before or after a student (that is, he is the first one or the last one), then he writes down number 0 instead (in Berland State University student IDs are numerated from 1).

After that, all the students went about their business. When they returned, they found out that restoring the queue is not such an easy task.

Help the students to restore the state of the queue by the numbers of the student ID's of their neighbors in the queue.


-----Input-----

The first line contains integer n (2 ≤ n ≤ 2·10^5) — the number of students in the queue. 

Then n lines follow, i-th line contains the pair of integers a_{i}, b_{i} (0 ≤ a_{i}, b_{i} ≤ 10^6), where a_{i} is the ID number of a person in front of a student and b_{i} is the ID number of a person behind a student. The lines are given in the arbitrary order. Value 0 is given instead of a neighbor's ID number if the neighbor doesn't exist.

The ID numbers of all students are distinct. It is guaranteed that the records correspond too the queue where all the students stand in some order.


-----Output-----

Print a sequence of n integers x_1, x_2, ..., x_{n} — the sequence of ID numbers of all the students in the order they go in the queue from the first student to the last one.


-----Examples-----
Input
4
92 31
0 7
31 0
7 141

Output
92 7 31 141 



-----Note-----

The picture illustrates the queue for the first sample. [Image]
user: Long ago, Vasily built a good fence at his country house. Vasily calls a fence good, if it is a series of n consecutively fastened vertical boards of centimeter width, the height of each in centimeters is a positive integer. The house owner remembers that the height of the i-th board to the left is h_{i}.

Today Vasily decided to change the design of the fence he had built, by cutting his top connected part so that the fence remained good. The cut part should consist of only the upper parts of the boards, while the adjacent parts must be interconnected (share a non-zero length before cutting out of the fence).

You, as Vasily's curious neighbor, will count the number of possible ways to cut exactly one part as is described above. Two ways to cut a part are called distinct, if for the remaining fences there is such i, that the height of the i-th boards vary.

As Vasily's fence can be very high and long, get the remainder after dividing the required number of ways by 1 000 000 007 (10^9 + 7).


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1 000 000) — the number of boards in Vasily's fence.

The second line contains n space-separated numbers h_1, h_2, ..., h_{n} (1 ≤ h_{i} ≤ 10^9), where h_{i} equals the height of the i-th board to the left.


-----Output-----

Print the remainder after dividing r by 1 000 000 007, where r is the number of ways to cut exactly one connected part so that the part consisted of the upper parts of the boards and the remaining fence was good.


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

Output
0

Input
3
3 4 2

Output
13



-----Note-----

From the fence from the first example it is impossible to cut exactly one piece so as the remaining fence was good.

All the possible variants of the resulting fence from the second sample look as follows (the grey shows the cut out part):  [Image]
user: There are b blocks of digits. Each one consisting of the same n digits, which are given to you in the input. Wet Shark must choose exactly one digit from each block and concatenate all of those digits together to form one large integer. For example, if he chooses digit 1 from the first block and digit 2 from the second block, he gets the integer 12. 

Wet Shark then takes this number modulo x. Please, tell him how many ways he can choose one digit from each block so that he gets exactly k as the final result. As this number may be too large, print it modulo 10^9 + 7.

Note, that the number of ways to choose some digit in the block is equal to the number of it's occurrences. For example, there are 3 ways to choose digit 5 from block 3 5 6 7 8 9 5 1 1 1 1 5.


-----Input-----

The first line of the input contains four space-separated integers, n, b, k and x (2 ≤ n ≤ 50 000, 1 ≤ b ≤ 10^9, 0 ≤ k < x ≤ 100, x ≥ 2) — the number of digits in one block, the number of blocks, interesting remainder modulo x and modulo x itself.

The next line contains n space separated integers a_{i} (1 ≤ a_{i} ≤ 9), that give the digits contained in each block.


-----Output-----

Print the number of ways to pick exactly one digit from each blocks, such that the resulting integer equals k modulo x.


-----Examples-----
Input
12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5

Output
3

Input
3 2 1 2
6 2 2

Output
0

Input
3 2 1 2
3 1 2

Output
6



-----Note-----

In the second sample possible integers are 22, 26, 62 and 66. None of them gives the remainder 1 modulo 2.

In the third sample integers 11, 13, 21, 23, 31 and 33 have remainder 1 modulo 2. There is exactly one way to obtain each of these integers, so the total answer is 6.
user: An exam for n students will take place in a long and narrow room, so the students will sit in a line in some order. The teacher suspects that students with adjacent numbers (i and i + 1) always studied side by side and became friends and if they take an exam sitting next to each other, they will help each other for sure.

Your task is to choose the maximum number of students and make such an arrangement of students in the room that no two students with adjacent numbers sit side by side.


-----Input-----

A single line contains integer n (1 ≤ n ≤ 5000) — the number of students at an exam.


-----Output-----

In the first line print integer k — the maximum number of students who can be seated so that no two students with adjacent numbers sit next to each other.

In the second line print k distinct integers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ n), where a_{i} is the number of the student on the i-th position. The students on adjacent positions mustn't have adjacent numbers. Formally, the following should be true: |a_{i} - a_{i} + 1| ≠ 1 for all i from 1 to k - 1.

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


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

Output
2
1 3
user: You are given a program you want to execute as a set of tasks organized in a dependency graph. The dependency graph is a directed acyclic graph: each task can depend on results of one or several other tasks, and there are no directed circular dependencies between tasks. A task can only be executed if all tasks it depends on have already completed.

Some of the tasks in the graph can only be executed on a coprocessor, and the rest can only be executed on the main processor. In one coprocessor call you can send it a set of tasks which can only be executed on it. For each task of the set, all tasks on which it depends must be either already completed or be included in the set. The main processor starts the program execution and gets the results of tasks executed on the coprocessor automatically.

Find the minimal number of coprocessor calls which are necessary to execute the given program.


-----Input-----

The first line contains two space-separated integers N (1 ≤ N ≤ 10^5) — the total number of tasks given, and M (0 ≤ M ≤ 10^5) — the total number of dependencies between tasks.

The next line contains N space-separated integers $E_{i} \in \{0,1 \}$. If E_{i} = 0, task i can only be executed on the main processor, otherwise it can only be executed on the coprocessor.

The next M lines describe the dependencies between tasks. Each line contains two space-separated integers T_1 and T_2 and means that task T_1 depends on task T_2 (T_1 ≠ T_2). Tasks are indexed from 0 to N - 1. All M pairs (T_1, T_2) are distinct. It is guaranteed that there are no circular dependencies between tasks.


-----Output-----

Output one line containing an integer — the minimal number of coprocessor calls necessary to execute the program.


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

Output
2

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

Output
1



-----Note-----

In the first test, tasks 1 and 3 can only be executed on the coprocessor. The dependency graph is linear, so the tasks must be executed in order 3 -> 2 -> 1 -> 0. You have to call coprocessor twice: first you call it for task 3, then you execute task 2 on the main processor, then you call it for for task 1, and finally you execute task 0 on the main processor.

In the second test, tasks 0, 1 and 2 can only be executed on the coprocessor. Tasks 1 and 2 have no dependencies, and task 0 depends on tasks 1 and 2, so all three tasks 0, 1 and 2 can be sent in one coprocessor call. After that task 3 is executed on the main processor.
user: A rare article in the Internet is posted without a possibility to comment it. On a Polycarp's website each article has comments feed.

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

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

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

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


-----Input-----

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

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

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


-----Output-----

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


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

Output
3
hello test one 
ok bye two 
a b 



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

Output
2
a 
A a A a A 



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

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




-----Note-----

The first example is explained in the statements.
user: n children are standing in a circle and playing the counting-out game. Children are numbered clockwise from 1 to n. In the beginning, the first child is considered the leader. The game is played in k steps. In the i-th step the leader counts out a_{i} people in clockwise order, starting from the next person. The last one to be pointed at by the leader is eliminated, and the next player after him becomes the new leader.

For example, if there are children with numbers [8, 10, 13, 14, 16] currently in the circle, the leader is child 13 and a_{i} = 12, then counting-out rhyme ends on child 16, who is eliminated. Child 8 becomes the leader.

You have to write a program which prints the number of the child to be eliminated on every step.


-----Input-----

The first line contains two integer numbers n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ n - 1).

The next line contains k integer numbers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print k numbers, the i-th one corresponds to the number of child to be eliminated at the i-th step.


-----Examples-----
Input
7 5
10 4 11 4 1

Output
4 2 5 6 1 

Input
3 2
2 5

Output
3 2 



-----Note-----

Let's consider first example:   In the first step child 4 is eliminated, child 5 becomes the leader.  In the second step child 2 is eliminated, child 3 becomes the leader.  In the third step child 5 is eliminated, child 6 becomes the leader.  In the fourth step child 6 is eliminated, child 7 becomes the leader.  In the final step child 1 is eliminated, child 3 becomes the leader.
user: Toastman came up with a very easy task. He gives it to Appleman, but Appleman doesn't know how to solve it. Can you help him?

Given a n × n checkerboard. Each cell of the board has either character 'x', or character 'o'. Is it true that each cell of the board has even number of adjacent cells with 'o'? Two cells of the board are adjacent if they share a side.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 100). Then n lines follow containing the description of the checkerboard. Each of them contains n characters (either 'x' or 'o') without spaces.


-----Output-----

Print "YES" or "NO" (without the quotes) depending on the answer to the problem.


-----Examples-----
Input
3
xxo
xox
oxx

Output
YES

Input
4
xxxo
xoxo
oxox
xxxx

Output
NO
user: One day Ms Swan bought an orange in a shop. The orange consisted of n·k segments, numbered with integers from 1 to n·k. 

There were k children waiting for Ms Swan at home. The children have recently learned about the orange and they decided to divide it between them. For that each child took a piece of paper and wrote the number of the segment that he would like to get: the i-th (1 ≤ i ≤ k) child wrote the number a_{i} (1 ≤ a_{i} ≤ n·k). All numbers a_{i} accidentally turned out to be different.

Now the children wonder, how to divide the orange so as to meet these conditions:  each child gets exactly n orange segments;  the i-th child gets the segment with number a_{i} for sure;  no segment goes to two children simultaneously. 

Help the children, divide the orange and fulfill the requirements, described above.


-----Input-----

The first line contains two integers n, k (1 ≤ n, k ≤ 30). The second line contains k space-separated integers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ n·k), where a_{i} is the number of the orange segment that the i-th child would like to get.

It is guaranteed that all numbers a_{i} are distinct.


-----Output-----

Print exactly n·k distinct integers. The first n integers represent the indexes of the segments the first child will get, the second n integers represent the indexes of the segments the second child will get, and so on. Separate the printed numbers with whitespaces.

You can print a child's segment indexes in any order. It is guaranteed that the answer always exists. If there are multiple correct answers, print any of them.


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

Output
2 4 
1 3 

Input
3 1
2

Output
3 2 1