meetforever/GRPO_CL huggingface dataset:
user: There are $n$ pillars aligned in a row and numbered from $1$ to $n$.

Initially each pillar contains exactly one disk. The $i$-th pillar contains a disk having radius $a_i$.

You can move these disks from one pillar to another. You can take a disk from pillar $i$ and place it on top of pillar $j$ if all these conditions are met:

  there is no other pillar between pillars $i$ and $j$. Formally, it means that $|i - j| = 1$;  pillar $i$ contains exactly one disk;  either pillar $j$ contains no disks, or the topmost disk on pillar $j$ has radius strictly greater than the radius of the disk you move. 

When you place a disk on a pillar that already has some disks on it, you put the new disk on top of previously placed disks, so the new disk will be used to check the third condition if you try to place another disk on the same pillar.

You may take any disk and place it on other pillar any number of times, provided that every time you do it, all three aforementioned conditions are met. Now you wonder, is it possible to place all $n$ disks on the same pillar simultaneously?


-----Input-----

The first line contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of pillars.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_i$ ($1 \le a_i \le n$), where $a_i$ is the radius of the disk initially placed on the $i$-th pillar. All numbers $a_i$ are distinct.


-----Output-----

Print YES if it is possible to place all the disks on the same pillar simultaneously, and NO otherwise. You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).


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

Output
YES

Input
3
3 1 2

Output
NO



-----Note-----

In the first case it is possible to place all disks on pillar $3$ using the following sequence of actions:

  take the disk with radius $3$ from pillar $2$ and place it on top of pillar $3$;  take the disk with radius $1$ from pillar $1$ and place it on top of pillar $2$;  take the disk with radius $2$ from pillar $4$ and place it on top of pillar $3$;  take the disk with radius $1$ from pillar $2$ and place it on top of pillar $3$.
user: Bill is a famous mathematician in BubbleLand. Thanks to his revolutionary math discoveries he was able to make enough money to build a beautiful house. Unfortunately, for not paying property tax on time, court decided to punish Bill by making him lose a part of his property.

Bill’s property can be observed as a convex regular 2n-sided polygon A_0 A_1... A_2n - 1 A_2n,  A_2n =  A_0, with sides of the exactly 1 meter in length. 

Court rules for removing part of his property are as follows:  Split every edge A_{k} A_{k} + 1,  k = 0... 2n - 1 in n equal parts of size 1 / n with points P_0, P_1, ..., P_{n} - 1  On every edge A_2k A_2k + 1,  k = 0... n - 1 court will choose one point B_2k =  P_{i} for some i = 0, ...,  n - 1 such that $\cup_{i = 0}^{n - 1} B_{2i} = \cup_{i = 0}^{n - 1} P_{i}$  On every edge A_2k + 1A_2k + 2,  k = 0...n - 1 Bill will choose one point B_2k + 1 =  P_{i} for some i = 0, ...,  n - 1 such that $\cup_{i = 0}^{n - 1} B_{2 i + 1} = \cup_{i = 0}^{n - 1} P_{i}$  Bill gets to keep property inside of 2n-sided polygon B_0 B_1... B_2n - 1 

Luckily, Bill found out which B_2k points the court chose. Even though he is a great mathematician, his house is very big and he has a hard time calculating. Therefore, he is asking you to help him choose points so he maximizes area of property he can keep.


-----Input-----

The first line contains one integer number n (2 ≤ n ≤ 50000), representing number of edges of 2n-sided polygon.

The second line contains n distinct integer numbers B_2k (0 ≤ B_2k ≤ n - 1,  k = 0... n - 1) separated by a single space, representing points the court chose. If B_2k = i, the court chose point P_{i} on side A_2k A_2k + 1.


-----Output-----

Output contains n distinct integers separated by a single space representing points B_1, B_3, ..., B_2n - 1 Bill should choose in order to maximize the property area. If there are multiple solutions that maximize the area, return any of them.


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

Output
0 2 1



-----Note-----

To maximize area Bill should choose points: B_1 = P_0, B_3 = P_2, B_5 = P_1

[Image]
user: Recently Monocarp got a job. His working day lasts exactly $m$ minutes. During work, Monocarp wants to drink coffee at certain moments: there are $n$ minutes $a_1, a_2, \dots, a_n$, when he is able and willing to take a coffee break (for the sake of simplicity let's consider that each coffee break lasts exactly one minute). 

However, Monocarp's boss doesn't like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute $a_i$, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least $d$ minutes pass between any two coffee breaks. Monocarp also wants to take these $n$ coffee breaks in a minimum possible number of working days (he doesn't count days when he is not at work, and he doesn't take coffee breaks on such days). Take into account that more than $d$ minutes pass between the end of any working day and the start of the following working day.

For each of the $n$ given minutes determine the day, during which Monocarp should take a coffee break in this minute. You have to minimize the number of days spent. 


-----Input-----

The first line contains three integers $n$, $m$, $d$ $(1 \le n \le 2\cdot10^{5}, n \le m \le 10^{9}, 1 \le d \le m)$ — the number of coffee breaks Monocarp wants to have, the length of each working day, and the minimum number of minutes between any two consecutive coffee breaks.

The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le m)$, where $a_i$ is some minute when Monocarp wants to have a coffee break.


-----Output-----

In the first line, write the minimum number of days required to make a coffee break in each of the $n$ given minutes. 

In the second line, print $n$ space separated integers. The $i$-th of integers should be the index of the day during which Monocarp should have a coffee break at minute $a_i$. Days are numbered from $1$. If there are multiple optimal solutions, you may print any of them.


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

Output
3
3 1 1 2 

Input
10 10 1
10 5 7 4 6 3 2 1 9 8

Output
2
2 1 1 2 2 1 2 1 1 2 



-----Note-----

In the first example, Monocarp can take two coffee breaks during the first day (during minutes $1$ and $5$, $3$ minutes will pass between these breaks). One break during the second day (at minute $2$), and one break during the third day (at minute $3$).

In the second example, Monocarp can determine the day of the break as follows: if the minute when he wants to take a break is odd, then this break is on the first day, if it is even, then this break is on the second day.
user: The Queen of England has n trees growing in a row in her garden. At that, the i-th (1 ≤ i ≤ n) tree from the left has height a_{i} meters. Today the Queen decided to update the scenery of her garden. She wants the trees' heights to meet the condition: for all i (1 ≤ i < n), a_{i} + 1 - a_{i} = k, where k is the number the Queen chose.

Unfortunately, the royal gardener is not a machine and he cannot fulfill the desire of the Queen instantly! In one minute, the gardener can either decrease the height of a tree to any positive integer height or increase the height of a tree to any positive integer height. How should the royal gardener act to fulfill a whim of Her Majesty in the minimum number of minutes?


-----Input-----

The first line contains two space-separated integers: n, k (1 ≤ n, k ≤ 1000). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000) — the heights of the trees in the row. 


-----Output-----

In the first line print a single integer p — the minimum number of minutes the gardener needs. In the next p lines print the description of his actions. 

If the gardener needs to increase the height of the j-th (1 ≤ j ≤ n) tree from the left by x (x ≥ 1) meters, then print in the corresponding line "+ j x". If the gardener needs to decrease the height of the j-th (1 ≤ j ≤ n) tree from the left by x (x ≥ 1) meters, print on the corresponding line "- j x".

If there are multiple ways to make a row of trees beautiful in the minimum number of actions, you are allowed to print any of them.


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

Output
2
+ 3 2
- 4 1

Input
4 1
1 2 3 4

Output
0
user: To make a paper airplane, one has to use a rectangular piece of paper. From a sheet of standard size you can make $s$ airplanes.

A group of $k$ people decided to make $n$ airplanes each. They are going to buy several packs of paper, each of them containing $p$ sheets, and then distribute the sheets between the people. Each person should have enough sheets to make $n$ airplanes. How many packs should they buy?


-----Input-----

The only line contains four integers $k$, $n$, $s$, $p$ ($1 \le k, n, s, p \le 10^4$) — the number of people, the number of airplanes each should make, the number of airplanes that can be made using one sheet and the number of sheets in one pack, respectively.


-----Output-----

Print a single integer — the minimum number of packs they should buy.


-----Examples-----
Input
5 3 2 3

Output
4

Input
5 3 100 1

Output
5



-----Note-----

In the first sample they have to buy $4$ packs of paper: there will be $12$ sheets in total, and giving $2$ sheets to each person is enough to suit everyone's needs.

In the second sample they have to buy a pack for each person as they can't share sheets.
user: After Vitaly was expelled from the university, he became interested in the graph theory.

Vitaly especially liked the cycles of an odd length in which each vertex occurs at most once.

Vitaly was wondering how to solve the following problem. You are given an undirected graph consisting of n vertices and m edges, not necessarily connected, without parallel edges and loops. You need to find t — the minimum number of edges that must be added to the given graph in order to form a simple cycle of an odd length, consisting of more than one vertex. Moreover, he must find w — the number of ways to add t edges in order to form a cycle of an odd length (consisting of more than one vertex). It is prohibited to add loops or parallel edges.

Two ways to add edges to the graph are considered equal if they have the same sets of added edges.

Since Vitaly does not study at the university, he asked you to help him with this task.


-----Input-----

The first line of the input contains two integers n and m ($3 \leq n \leq 10^{5}, 0 \leq m \leq \operatorname{min}(\frac{n(n - 1)}{2}, 10^{5})$ — the number of vertices in the graph and the number of edges in the graph.

Next m lines contain the descriptions of the edges of the graph, one edge per line. Each edge is given by a pair of integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n) — the vertices that are connected by the i-th edge. All numbers in the lines are separated by a single space.

It is guaranteed that the given graph doesn't contain any loops and parallel edges. The graph isn't necessarily connected.


-----Output-----

Print in the first line of the output two space-separated integers t and w — the minimum number of edges that should be added to the graph to form a simple cycle of an odd length consisting of more than one vertex where each vertex occurs at most once, and the number of ways to do this.


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

Output
1 2

Input
3 3
1 2
2 3
3 1

Output
0 1

Input
3 0

Output
3 1



-----Note-----

The simple cycle is a cycle that doesn't contain any vertex twice.
user: You are given a positive integer $m$ and two integer sequence: $a=[a_1, a_2, \ldots, a_n]$ and $b=[b_1, b_2, \ldots, b_n]$. Both of these sequence have a length $n$.

Permutation is a sequence of $n$ different positive integers from $1$ to $n$. For example, these sequences are permutations: $[1]$, $[1,2]$, $[2,1]$, $[6,7,3,4,1,2,5]$. These are not: $[0]$, $[1,1]$, $[2,3]$.

You need to find the non-negative integer $x$, and increase all elements of $a_i$ by $x$, modulo $m$ (i.e. you want to change $a_i$ to $(a_i + x) \bmod m$), so it would be possible to rearrange elements of $a$ to make it equal $b$, among them you need to find the smallest possible $x$.

In other words, you need to find the smallest non-negative integer $x$, for which it is possible to find some permutation $p=[p_1, p_2, \ldots, p_n]$, such that for all $1 \leq i \leq n$, $(a_i + x) \bmod m = b_{p_i}$, where $y \bmod m$ — remainder of division of $y$ by $m$.

For example, if $m=3$, $a = [0, 0, 2, 1], b = [2, 0, 1, 1]$, you can choose $x=1$, and $a$ will be equal to $[1, 1, 0, 2]$ and you can rearrange it to make it equal $[2, 0, 1, 1]$, which is equal to $b$.


-----Input-----

The first line contains two integers $n,m$ ($1 \leq n \leq 2000, 1 \leq m \leq 10^9$): number of elemens in arrays and $m$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < m$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i < m$).

It is guaranteed that there exists some non-negative integer $x$, such that it would be possible to find some permutation $p_1, p_2, \ldots, p_n$ such that $(a_i + x) \bmod m = b_{p_i}$.


-----Output-----

Print one integer, the smallest non-negative integer $x$, such that it would be possible to find some permutation $p_1, p_2, \ldots, p_n$ such that $(a_i + x) \bmod m = b_{p_i}$ for all $1 \leq i \leq n$.


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

Output
1

Input
3 2
0 0 0
1 1 1

Output
1

Input
5 10
0 0 0 1 2
2 1 0 0 0

Output
0
user: Hideo Kojima has just quit his job at Konami. Now he is going to find a new place to work. Despite being such a well-known person, he still needs a CV to apply for a job.

During all his career Hideo has produced n games. Some of them were successful, some were not. Hideo wants to remove several of them (possibly zero) from his CV to make a better impression on employers. As a result there should be no unsuccessful game which comes right after successful one in his CV.

More formally, you are given an array s_1, s_2, ..., s_{n} of zeros and ones. Zero corresponds to an unsuccessful game, one — to a successful one. Games are given in order they were produced, and Hideo can't swap these values. He should remove some elements from this array in such a way that no zero comes right after one.

Besides that, Hideo still wants to mention as much games in his CV as possible. Help this genius of a man determine the maximum number of games he can leave in his CV.


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 100).

The second line contains n space-separated integer numbers s_1, s_2, ..., s_{n} (0 ≤ s_{i} ≤ 1). 0 corresponds to an unsuccessful game, 1 — to a successful one.


-----Output-----

Print one integer — the maximum number of games Hideo can leave in his CV so that no unsuccessful game comes after a successful one.


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

Output
3

Input
6
0 1 0 0 1 0

Output
4

Input
1
0

Output
1
user: The problem describes the properties of a command line. The description somehow resembles the one you usually see in real operating systems. However, there are differences in the behavior. Please make sure you've read the statement attentively and use it as a formal document.

In the Pindows operating system a strings are the lexemes of the command line — the first of them is understood as the name of the program to run and the following lexemes are its arguments. For example, as we execute the command " run.exe one, two . ", we give four lexemes to the Pindows command line: "run.exe", "one,", "two", ".". More formally, if we run a command that can be represented as string s (that has no quotes), then the command line lexemes are maximal by inclusion substrings of string s that contain no spaces.

To send a string with spaces or an empty string as a command line lexeme, we can use double quotes. The block of characters that should be considered as one lexeme goes inside the quotes. Embedded quotes are prohibited — that is, for each occurrence of character """ we should be able to say clearly that the quotes are opening or closing. For example, as we run the command ""run.exe o" "" " ne, " two . " " ", we give six lexemes to the Pindows command line: "run.exe o", "" (an empty string), " ne, ", "two", ".", " " (a single space).

It is guaranteed that each lexeme of the command line is either surrounded by spaces on both sides or touches the corresponding command border. One of its consequences is: the opening brackets are either the first character of the string or there is a space to the left of them.

You have a string that consists of uppercase and lowercase English letters, digits, characters ".,?!"" and spaces. It is guaranteed that this string is a correct OS Pindows command line string. Print all lexemes of this command line string. Consider the character """ to be used only in order to denote a single block of characters into one command line lexeme. In particular, the consequence is that the given string has got an even number of such characters.


-----Input-----

The single line contains a non-empty string s. String s consists of at most 10^5 characters. Each character is either an uppercase or a lowercase English letter, or a digit, or one of the ".,?!"" signs, or a space.

It is guaranteed that the given string is some correct command line string of the OS Pindows. It is guaranteed that the given command line string contains at least one lexeme.


-----Output-----

In the first line print the first lexeme, in the second line print the second one and so on. To make the output clearer, print the "<" (less) character to the left of your lexemes and the ">" (more) character to the right. Print the lexemes in the order in which they occur in the command.

Please, follow the given output format strictly. For more clarifications on the output format see the test samples.


-----Examples-----
Input
"RUn.exe O" "" "   2ne, " two! . " "

Output
<RUn.exe O>
<>
<   2ne, >
<two!>
<.>
< >

Input
   firstarg   second   ""    

Output
<firstarg>
<second>
<>
user: Bob is decorating his kitchen, more precisely, the floor. He has found a prime candidate for the tiles he will use. They come in a simple form factor — a square tile that is diagonally split into white and black part as depicted in the figure below. [Image] 

The dimension of this tile is perfect for this kitchen, as he will need exactly $w \times h$ tiles without any scraps. That is, the width of the kitchen is $w$ tiles, and the height is $h$ tiles. As each tile can be rotated in one of four ways, he still needs to decide on how exactly he will tile the floor. There is a single aesthetic criterion that he wants to fulfil: two adjacent tiles must not share a colour on the edge — i.e. one of the tiles must have a white colour on the shared border, and the second one must be black. [Image] The picture on the left shows one valid tiling of a $3 \times 2$ kitchen. The picture on the right shows an invalid arrangement, as the bottom two tiles touch with their white parts. 

Find the number of possible tilings. As this number may be large, output its remainder when divided by $998244353$ (a prime number). 


-----Input-----

The only line contains two space separated integers $w$, $h$ ($1 \leq w,h \leq 1\,000$) — the width and height of the kitchen, measured in tiles.


-----Output-----

Output a single integer $n$ — the remainder of the number of tilings when divided by $998244353$.


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

Output
16

Input
2 4

Output
64
user: New Year is coming in Line World! In this world, there are n cells numbered by integers from 1 to n, as a 1 × n board. People live in cells. However, it was hard to move between distinct cells, because of the difficulty of escaping the cell. People wanted to meet people who live in other cells.

So, user tncks0121 has made a transportation system to move between these cells, to celebrate the New Year. First, he thought of n - 1 positive integers a_1, a_2, ..., a_{n} - 1. For every integer i where 1 ≤ i ≤ n - 1 the condition 1 ≤ a_{i} ≤ n - i holds. Next, he made n - 1 portals, numbered by integers from 1 to n - 1. The i-th (1 ≤ i ≤ n - 1) portal connects cell i and cell (i + a_{i}), and one can travel from cell i to cell (i + a_{i}) using the i-th portal. Unfortunately, one cannot use the portal backwards, which means one cannot move from cell (i + a_{i}) to cell i using the i-th portal. It is easy to see that because of condition 1 ≤ a_{i} ≤ n - i one can't leave the Line World using portals.

Currently, I am standing at cell 1, and I want to go to cell t. However, I don't know whether it is possible to go there. Please determine whether I can go to cell t by only using the construted transportation system.


-----Input-----

The first line contains two space-separated integers n (3 ≤ n ≤ 3 × 10^4) and t (2 ≤ t ≤ n) — the number of cells, and the index of the cell which I want to go to.

The second line contains n - 1 space-separated integers a_1, a_2, ..., a_{n} - 1 (1 ≤ a_{i} ≤ n - i). It is guaranteed, that using the given transportation system, one cannot leave the Line World.


-----Output-----

If I can go to cell t using the transportation system, print "YES". Otherwise, print "NO".


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

Output
YES

Input
8 5
1 2 1 2 1 1 1

Output
NO



-----Note-----

In the first sample, the visited cells are: 1, 2, 4; so we can successfully visit the cell 4.

In the second sample, the possible cells to visit are: 1, 2, 4, 6, 7, 8; so we can't visit the cell 5, which we want to visit.
user: Ashish has a tree consisting of $n$ nodes numbered $1$ to $n$ rooted at node $1$. The $i$-th node in the tree has a cost $a_i$, and binary digit $b_i$ is written in it. He wants to have binary digit $c_i$ written in the $i$-th node in the end.

To achieve this, he can perform the following operation any number of times:   Select any $k$ nodes from the subtree of any node $u$, and shuffle the digits in these nodes as he wishes, incurring a cost of $k \cdot a_u$. Here, he can choose $k$ ranging from $1$ to the size of the subtree of $u$. 

He wants to perform the operations in such a way that every node finally has the digit corresponding to its target.

Help him find the minimum total cost he needs to spend so that after all the operations, every node $u$ has digit $c_u$ written in it, or determine that it is impossible.


-----Input-----

First line contains a single integer $n$ $(1 \le n \le 2 \cdot 10^5)$ denoting the number of nodes in the tree.

$i$-th line of the next $n$ lines contains 3 space-separated integers $a_i$, $b_i$, $c_i$ $(1 \leq a_i \leq 10^9, 0 \leq b_i, c_i \leq 1)$  — the cost of the $i$-th node, its initial digit and its goal digit.

Each of the next $n - 1$ lines contain two integers $u$, $v$ $(1 \leq u, v \leq n, \text{ } u \ne v)$, meaning that there is an edge between nodes $u$ and $v$ in the tree.


-----Output-----

Print the minimum total cost to make every node reach its target digit, and $-1$ if it is impossible.


-----Examples-----
Input
5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5

Output
4
Input
5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5

Output
24000
Input
2
109 0 1
205 0 1
1 2

Output
-1


-----Note-----

The tree corresponding to samples $1$ and $2$ are: [Image]

In sample $1$, we can choose node $1$ and $k = 4$ for a cost of $4 \cdot 1$ = $4$ and select nodes ${1, 2, 3, 5}$, shuffle their digits and get the desired digits in every node.

In sample $2$, we can choose node $1$ and $k = 2$ for a cost of $10000 \cdot 2$, select nodes ${1, 5}$ and exchange their digits, and similarly, choose node $2$ and $k = 2$ for a cost of $2000 \cdot 2$, select nodes ${2, 3}$ and exchange their digits to get the desired digits in every node.

In sample $3$, it is impossible to get the desired digits, because there is no node with digit $1$ initially.