meetforever/GRPO_CL huggingface dataset:
user: Iahub wants to enhance his multitasking abilities. In order to do this, he wants to sort n arrays simultaneously, each array consisting of m integers.

Iahub can choose a pair of distinct indices i and j (1 ≤ i, j ≤ m, i ≠ j). Then in each array the values at positions i and j are swapped only if the value at position i is strictly greater than the value at position j.

Iahub wants to find an array of pairs of distinct indices that, chosen in order, sort all of the n arrays in ascending or descending order (the particular order is given in input). The size of the array can be at most $\frac{m(m - 1)}{2}$ (at most $\frac{m(m - 1)}{2}$ pairs). Help Iahub, find any suitable array.


-----Input-----

The first line contains three integers n (1 ≤  n ≤ 1000), m (1 ≤ m ≤  100) and k. Integer k is 0 if the arrays must be sorted in ascending order, and 1 if the arrays must be sorted in descending order. Each line i of the next n lines contains m integers separated by a space, representing the i-th array. For each element x of the array i, 1 ≤ x ≤ 10^6 holds.


-----Output-----

On the first line of the output print an integer p, the size of the array (p can be at most $\frac{m(m - 1)}{2}$). Each of the next p lines must contain two distinct integers i and j (1 ≤ i, j ≤ m, i ≠ j), representing the chosen indices.

If there are multiple correct answers, you can print any.


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

Output
3
2 4
2 3
4 5

Input
3 2 1
1 2
2 3
3 4

Output
1
2 1



-----Note-----

Consider the first sample. After the first operation, the arrays become [1, 3, 2, 5, 4] and [1, 2, 3, 4, 5]. After the second operation, the arrays become [1, 2, 3, 5, 4] and [1, 2, 3, 4, 5]. After the third operation they become [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5].
user: A binary matrix is called good if every even length square sub-matrix has an odd number of ones. 

Given a binary matrix $a$ consisting of $n$ rows and $m$ columns, determine the minimum number of cells you need to change to make it good, or report that there is no way to make it good at all. 

All the terms above have their usual meanings — refer to the Notes section for their formal definitions. 


-----Input-----

The first line of input contains two integers $n$ and $m$ ($1 \leq n \leq m \leq 10^6$ and $n\cdot m \leq 10^6$)  — the number of rows and columns in $a$, respectively. 

The following $n$ lines each contain $m$ characters, each of which is one of 0 and 1. If the $j$-th character on the $i$-th line is 1, then $a_{i,j} = 1$. Similarly, if the $j$-th character on the $i$-th line is 0, then $a_{i,j} = 0$.


-----Output-----

Output the minimum number of cells you need to change to make $a$ good, or output $-1$ if it's not possible at all.


-----Examples-----
Input
3 3
101
001
110

Output
2
Input
7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011

Output
-1


-----Note-----

In the first case, changing $a_{1,1}$ to $0$ and $a_{2,2}$ to $1$ is enough. 

You can verify that there is no way to make the matrix in the second case good. 

Some definitions —   A binary matrix is one in which every element is either $1$ or $0$.  A sub-matrix is described by $4$ parameters — $r_1$, $r_2$, $c_1$, and $c_2$; here, $1 \leq r_1 \leq r_2 \leq n$ and $1 \leq c_1 \leq c_2 \leq m$.  This sub-matrix contains all elements $a_{i,j}$ that satisfy both $r_1 \leq i \leq r_2$ and $c_1 \leq j \leq c_2$.  A sub-matrix is, further, called an even length square if $r_2-r_1 = c_2-c_1$ and $r_2-r_1+1$ is divisible by $2$.
user: Sonya decided to organize an exhibition of flowers. Since the girl likes only roses and lilies, she decided that only these two kinds of flowers should be in this exhibition.

There are $n$ flowers in a row in the exhibition. Sonya can put either a rose or a lily in the $i$-th position. Thus each of $n$ positions should contain exactly one flower: a rose or a lily.

She knows that exactly $m$ people will visit this exhibition. The $i$-th visitor will visit all flowers from $l_i$ to $r_i$ inclusive. The girl knows that each segment has its own beauty that is equal to the product of the number of roses and the number of lilies.

Sonya wants her exhibition to be liked by a lot of people. That is why she wants to put the flowers in such way that the sum of beauties of all segments would be maximum possible.


-----Input-----

The first line contains two integers $n$ and $m$ ($1\leq n, m\leq 10^3$) — the number of flowers and visitors respectively.

Each of the next $m$ lines contains two integers $l_i$ and $r_i$ ($1\leq l_i\leq r_i\leq n$), meaning that $i$-th visitor will visit all flowers from $l_i$ to $r_i$ inclusive.


-----Output-----

Print the string of $n$ characters. The $i$-th symbol should be «0» if you want to put a rose in the $i$-th position, otherwise «1» if you want to put a lily.

If there are multiple answers, print any.


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

Output
01100
Input
6 3
5 6
1 4
4 6

Output
110010


-----Note-----

In the first example, Sonya can put roses in the first, fourth, and fifth positions, and lilies in the second and third positions;

  in the segment $[1\ldots3]$, there are one rose and two lilies, so the beauty is equal to $1\cdot 2=2$;  in the segment $[2\ldots4]$, there are one rose and two lilies, so the beauty is equal to $1\cdot 2=2$;  in the segment $[2\ldots5]$, there are two roses and two lilies, so the beauty is equal to $2\cdot 2=4$. 

The total beauty is equal to $2+2+4=8$.

In the second example, Sonya can put roses in the third, fourth, and sixth positions, and lilies in the first, second, and fifth positions;

  in the segment $[5\ldots6]$, there are one rose and one lily, so the beauty is equal to $1\cdot 1=1$;  in the segment $[1\ldots4]$, there are two roses and two lilies, so the beauty is equal to $2\cdot 2=4$;  in the segment $[4\ldots6]$, there are two roses and one lily, so the beauty is equal to $2\cdot 1=2$. 

The total beauty is equal to $1+4+2=7$.
user: Valera has got a rectangle table consisting of n rows and m columns. Valera numbered the table rows starting from one, from top to bottom and the columns – starting from one, from left to right. We will represent cell that is on the intersection of row x and column y by a pair of integers (x, y).

Valera wants to place exactly k tubes on his rectangle table. A tube is such sequence of table cells (x_1, y_1), (x_2, y_2), ..., (x_{r}, y_{r}), that:   r ≥ 2;  for any integer i (1 ≤ i ≤ r - 1) the following equation |x_{i} - x_{i} + 1| + |y_{i} - y_{i} + 1| = 1 holds;  each table cell, which belongs to the tube, must occur exactly once in the sequence. 

Valera thinks that the tubes are arranged in a fancy manner if the following conditions are fulfilled:   no pair of tubes has common cells;  each cell of the table belongs to some tube. 

Help Valera to arrange k tubes on his rectangle table in a fancy manner.


-----Input-----

The first line contains three space-separated integers n, m, k (2 ≤ n, m ≤ 300; 2 ≤ 2k ≤ n·m) — the number of rows, the number of columns and the number of tubes, correspondingly. 


-----Output-----

Print k lines. In the i-th line print the description of the i-th tube: first print integer r_{i} (the number of tube cells), then print 2r_{i} integers x_{i}1, y_{i}1, x_{i}2, y_{i}2, ..., x_{ir}_{i}, y_{ir}_{i} (the sequence of table cells).

If there are multiple solutions, you can print any of them. It is guaranteed that at least one solution exists. 


-----Examples-----
Input
3 3 3

Output
3 1 1 1 2 1 3
3 2 1 2 2 2 3
3 3 1 3 2 3 3

Input
2 3 1

Output
6 1 1 1 2 1 3 2 3 2 2 2 1



-----Note-----

Picture for the first sample:  [Image] 

Picture for the second sample:  [Image]
user: You are given a positive integer $D$. Let's build the following graph from it:   each vertex is a divisor of $D$ (not necessarily prime, $1$ and $D$ itself are also included);  two vertices $x$ and $y$ ($x > y$) have an undirected edge between them if $x$ is divisible by $y$ and $\frac x y$ is a prime;  the weight of an edge is the number of divisors of $x$ that are not divisors of $y$. 

For example, here is the graph for $D=12$:  [Image] 

Edge $(4,12)$ has weight $3$ because $12$ has divisors $[1,2,3,4,6,12]$ and $4$ has divisors $[1,2,4]$. Thus, there are $3$ divisors of $12$ that are not divisors of $4$ — $[3,6,12]$.

There is no edge between $3$ and $2$ because $3$ is not divisible by $2$. There is no edge between $12$ and $3$ because $\frac{12}{3}=4$ is not a prime.

Let the length of the path between some vertices $v$ and $u$ in the graph be the total weight of edges on it. For example, path $[(1, 2), (2, 6), (6, 12), (12, 4), (4, 2), (2, 6)]$ has length $1+2+2+3+1+2=11$. The empty path has length $0$.

So the shortest path between two vertices $v$ and $u$ is the path that has the minimal possible length.

Two paths $a$ and $b$ are different if there is either a different number of edges in them or there is a position $i$ such that $a_i$ and $b_i$ are different edges.

You are given $q$ queries of the following form:   $v$ $u$ — calculate the number of the shortest paths between vertices $v$ and $u$. 

The answer for each query might be large so print it modulo $998244353$.


-----Input-----

The first line contains a single integer $D$ ($1 \le D \le 10^{15}$) — the number the graph is built from.

The second line contains a single integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

Each of the next $q$ lines contains two integers $v$ and $u$ ($1 \le v, u \le D$). It is guaranteed that $D$ is divisible by both $v$ and $u$ (both $v$ and $u$ are divisors of $D$).


-----Output-----

Print $q$ integers — for each query output the number of the shortest paths between the two given vertices modulo $998244353$.


-----Examples-----
Input
12
3
4 4
12 1
3 4

Output
1
3
1

Input
1
1
1 1

Output
1

Input
288807105787200
4
46 482955026400
12556830686400 897
414 12556830686400
4443186242880 325

Output
547558588
277147129
457421435
702277623



-----Note-----

In the first example:   The first query is only the empty path — length $0$;  The second query are paths $[(12, 4), (4, 2), (2, 1)]$ (length $3+1+1=5$), $[(12, 6), (6, 2), (2, 1)]$ (length $2+2+1=5$) and $[(12, 6), (6, 3), (3, 1)]$ (length $2+2+1=5$).  The third query is only the path $[(3, 1), (1, 2), (2, 4)]$ (length $1+1+1=3$).
user: General Payne has a battalion of n soldiers. The soldiers' beauty contest is coming up, it will last for k days. Payne decided that his battalion will participate in the pageant. Now he has choose the participants.

All soldiers in the battalion have different beauty that is represented by a positive integer. The value a_{i} represents the beauty of the i-th soldier.

On each of k days Generals has to send a detachment of soldiers to the pageant. The beauty of the detachment is the sum of the beauties of the soldiers, who are part of this detachment. Payne wants to surprise the jury of the beauty pageant, so each of k days the beauty of the sent detachment should be unique. In other words, all k beauties of the sent detachments must be distinct numbers.

Help Payne choose k detachments of different beauties for the pageant. Please note that Payne cannot just forget to send soldiers on one day, that is, the detachment of soldiers he sends to the pageant should never be empty.


-----Input-----

The first line contains two integers n, k (1 ≤ n ≤ 50; 1 ≤ k ≤  $\frac{n(n + 1)}{2}$) — the number of soldiers and the number of days in the pageant, correspondingly. The second line contains space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^7) — the beauties of the battalion soldiers.

It is guaranteed that Payne's battalion doesn't have two soldiers with the same beauty.


-----Output-----

Print k lines: in the i-th line print the description of the detachment that will participate in the pageant on the i-th day. The description consists of integer c_{i} (1 ≤ c_{i} ≤ n) — the number of soldiers in the detachment on the i-th day of the pageant and c_{i} distinct integers p_{1, }i, p_{2, }i, ..., p_{c}_{i}, i — the beauties of the soldiers in the detachment on the i-th day of the pageant. The beauties of the soldiers are allowed to print in any order.

Separate numbers on the lines by spaces. It is guaranteed that there is the solution that meets the problem conditions. If there are multiple solutions, print any of them.


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

Output
1 1
1 2
2 3 2

Input
2 1
7 12

Output
1 12
user: You are given an integer $n$ and an integer $k$.

In one step you can do one of the following moves:   decrease $n$ by $1$;  divide $n$ by $k$ if $n$ is divisible by $k$. 

For example, if $n = 27$ and $k = 3$ you can do the following steps: $27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$.

You are asked to calculate the minimum number of steps to reach $0$ from $n$. 


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of queries.

The only line of each query contains two integers $n$ and $k$ ($1 \le n \le 10^{18}$, $2 \le k \le 10^{18}$).


-----Output-----

For each query print the minimum number of steps to reach $0$ from $n$ in single line. 


-----Example-----
Input
2
59 3
1000000000000000000 10

Output
8
19



-----Note-----

Steps for the first test case are: $59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$.

In the second test case you have to divide $n$ by $k$ $18$ times and then decrease $n$ by $1$.
user: There are $n$ emotes in very popular digital collectible card game (the game is pretty famous so we won't say its name). The $i$-th emote increases the opponent's happiness by $a_i$ units (we all know that emotes in this game are used to make opponents happy).

You have time to use some emotes only $m$ times. You are allowed to use any emotion once, more than once, or not use it at all. The only restriction is that you cannot use the same emote more than $k$ times in a row (otherwise the opponent will think that you're trolling him).

Note that two emotes $i$ and $j$ ($i \ne j$) such that $a_i = a_j$ are considered different.

You have to make your opponent as happy as possible. Find the maximum possible opponent's happiness.


-----Input-----

The first line of the input contains three integers $n, m$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le m \le 2 \cdot 10^9$) — the number of emotes, the number of times you can use emotes and the maximum number of times you may use the same emote in a row.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is value of the happiness of the $i$-th emote.


-----Output-----

Print one integer — the maximum opponent's happiness if you use emotes in a way satisfying the problem statement.


-----Examples-----
Input
6 9 2
1 3 3 7 4 2

Output
54

Input
3 1000000000 1
1000000000 987654321 1000000000

Output
1000000000000000000



-----Note-----

In the first example you may use emotes in the following sequence: $4, 4, 5, 4, 4, 5, 4, 4, 5$.
user: You a captain of a ship. Initially you are standing in a point $(x_1, y_1)$ (obviously, all positions in the sea can be described by cartesian plane) and you want to travel to a point $(x_2, y_2)$. 

You know the weather forecast — the string $s$ of length $n$, consisting only of letters U, D, L and R. The letter corresponds to a direction of wind. Moreover, the forecast is periodic, e.g. the first day wind blows to the side $s_1$, the second day — $s_2$, the $n$-th day — $s_n$ and $(n+1)$-th day — $s_1$ again and so on. 

Ship coordinates change the following way:  if wind blows the direction U, then the ship moves from $(x, y)$ to $(x, y + 1)$;  if wind blows the direction D, then the ship moves from $(x, y)$ to $(x, y - 1)$;  if wind blows the direction L, then the ship moves from $(x, y)$ to $(x - 1, y)$;  if wind blows the direction R, then the ship moves from $(x, y)$ to $(x + 1, y)$. 

The ship can also either go one of the four directions or stay in place each day. If it goes then it's exactly 1 unit of distance. Transpositions of the ship and the wind add up. If the ship stays in place, then only the direction of wind counts. For example, if wind blows the direction U and the ship moves the direction L, then from point $(x, y)$ it will move to the point $(x - 1, y + 1)$, and if it goes the direction U, then it will move to the point $(x, y + 2)$.

You task is to determine the minimal number of days required for the ship to reach the point $(x_2, y_2)$.


-----Input-----

The first line contains two integers $x_1, y_1$ ($0 \le x_1, y_1 \le 10^9$) — the initial coordinates of the ship.

The second line contains two integers $x_2, y_2$ ($0 \le x_2, y_2 \le 10^9$) — the coordinates of the destination point.

It is guaranteed that the initial coordinates and destination point coordinates are different.

The third line contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the string $s$.

The fourth line contains the string $s$ itself, consisting only of letters U, D, L and R.


-----Output-----

The only line should contain the minimal number of days required for the ship to reach the point $(x_2, y_2)$.

If it's impossible then print "-1".


-----Examples-----
Input
0 0
4 6
3
UUU

Output
5

Input
0 3
0 0
3
UDD

Output
3

Input
0 0
0 1
1
L

Output
-1



-----Note-----

In the first example the ship should perform the following sequence of moves: "RRRRU". Then its coordinates will change accordingly: $(0, 0)$ $\rightarrow$ $(1, 1)$ $\rightarrow$ $(2, 2)$ $\rightarrow$ $(3, 3)$ $\rightarrow$ $(4, 4)$ $\rightarrow$ $(4, 6)$.

In the second example the ship should perform the following sequence of moves: "DD" (the third day it should stay in place). Then its coordinates will change accordingly: $(0, 3)$ $\rightarrow$ $(0, 3)$ $\rightarrow$ $(0, 1)$ $\rightarrow$ $(0, 0)$.

In the third example the ship can never reach the point $(0, 1)$.
user: Now Serval is a junior high school student in Japari Middle School, and he is still thrilled on math as before. 

As a talented boy in mathematics, he likes to play with numbers. This time, he wants to play with numbers on a rooted tree.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a node $v$ is the last different from $v$ vertex on the path from the root to the vertex $v$. Children of vertex $v$ are all nodes for which $v$ is the parent. A vertex is a leaf if it has no children.

The rooted tree Serval owns has $n$ nodes, node $1$ is the root. Serval will write some numbers into all nodes of the tree. However, there are some restrictions. Each of the nodes except leaves has an operation $\max$ or $\min$ written in it, indicating that the number in this node should be equal to the maximum or minimum of all the numbers in its sons, respectively. 

Assume that there are $k$ leaves in the tree. Serval wants to put integers $1, 2, \ldots, k$ to the $k$ leaves (each number should be used exactly once). He loves large numbers, so he wants to maximize the number in the root. As his best friend, can you help him?


-----Input-----

The first line contains an integer $n$ ($2 \leq n \leq 3\cdot 10^5$), the size of the tree.

The second line contains $n$ integers, the $i$-th of them represents the operation in the node $i$. $0$ represents $\min$ and $1$ represents $\max$. If the node is a leaf, there is still a number of $0$ or $1$, but you can ignore it.

The third line contains $n-1$ integers $f_2, f_3, \ldots, f_n$ ($1 \leq f_i \leq i-1$), where $f_i$ represents the parent of the node $i$.


-----Output-----

Output one integer — the maximum possible number in the root of the tree.


-----Examples-----
Input
6
1 0 1 1 0 1
1 2 2 2 2

Output
1

Input
5
1 0 1 0 1
1 1 1 1

Output
4

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

Output
4

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

Output
5



-----Note-----

Pictures below explain the examples. The numbers written in the middle of the nodes are their indices, and the numbers written on the top are the numbers written in the nodes.

In the first example, no matter how you arrange the numbers, the answer is $1$. [Image] 

In the second example, no matter how you arrange the numbers, the answer is $4$. [Image] 

In the third example, one of the best solution to achieve $4$ is to arrange $4$ and $5$ to nodes $4$ and $5$. [Image] 

In the fourth example, the best solution is to arrange $5$ to node $5$. [Image]
user: You're given a tree with $n$ vertices.

Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^5$) denoting the size of the tree. 

The next $n - 1$ lines contain two integers $u$, $v$ ($1 \le u, v \le n$) each, describing the vertices connected by the $i$-th edge.

It's guaranteed that the given edges form a tree.


-----Output-----

Output a single integer $k$ — the maximum number of edges that can be removed to leave all connected components with even size, or $-1$ if it is impossible to remove edges in order to satisfy this property.


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

Output
1
Input
3
1 2
1 3

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

Output
4
Input
2
1 2

Output
0


-----Note-----

In the first example you can remove the edge between vertices $1$ and $4$. The graph after that will have two connected components with two vertices in each.

In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is $-1$.
user: Paladin Manao caught the trail of the ancient Book of Evil in a swampy area. This area contains n settlements numbered from 1 to n. Moving through the swamp is very difficult, so people tramped exactly n - 1 paths. Each of these paths connects some pair of settlements and is bidirectional. Moreover, it is possible to reach any settlement from any other one by traversing one or several paths.

The distance between two settlements is the minimum number of paths that have to be crossed to get from one settlement to the other one. Manao knows that the Book of Evil has got a damage range d. This means that if the Book of Evil is located in some settlement, its damage (for example, emergence of ghosts and werewolves) affects other settlements at distance d or less from the settlement where the Book resides.

Manao has heard of m settlements affected by the Book of Evil. Their numbers are p_1, p_2, ..., p_{m}. Note that the Book may be affecting other settlements as well, but this has not been detected yet. Manao wants to determine which settlements may contain the Book. Help him with this difficult task.


-----Input-----

The first line contains three space-separated integers n, m and d (1 ≤ m ≤ n ≤ 100000; 0 ≤ d ≤ n - 1). The second line contains m distinct space-separated integers p_1, p_2, ..., p_{m} (1 ≤ p_{i} ≤ n). Then n - 1 lines follow, each line describes a path made in the area. A path is described by a pair of space-separated integers a_{i} and b_{i} representing the ends of this path.


-----Output-----

Print a single number — the number of settlements that may contain the Book of Evil. It is possible that Manao received some controversial information and there is no settlement that may contain the Book. In such case, print 0.


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

Output
3



-----Note-----

Sample 1. The damage range of the Book of Evil equals 3 and its effects have been noticed in settlements 1 and 2. Thus, it can be in settlements 3, 4 or 5.

 [Image]