meetforever/GRPO_CL huggingface dataset:
user: ZS the Coder loves mazes. Your job is to create one so that he can play with it. A maze consists of n × m rooms, and the rooms are arranged in n rows (numbered from the top to the bottom starting from 1) and m columns (numbered from the left to the right starting from 1). The room in the i-th row and j-th column is denoted by (i, j). A player starts in the room (1, 1) and wants to reach the room (n, m).

Each room has four doors (except for ones at the maze border), one on each of its walls, and two adjacent by the wall rooms shares the same door. Some of the doors are locked, which means it is impossible to pass through the door. For example, if the door connecting (i, j) and (i, j + 1) is locked, then we can't go from (i, j) to (i, j + 1). Also, one can only travel between the rooms downwards (from the room (i, j) to the room (i + 1, j)) or rightwards (from the room (i, j) to the room (i, j + 1)) provided the corresponding door is not locked. [Image] This image represents a maze with some doors locked. The colored arrows denotes all the possible paths while a red cross denotes a locked door. 

ZS the Coder considers a maze to have difficulty x if there is exactly x ways of travelling from the room (1, 1) to the room (n, m). Two ways are considered different if they differ by the sequence of rooms visited while travelling.

Your task is to create a maze such that its difficulty is exactly equal to T. In addition, ZS the Coder doesn't like large mazes, so the size of the maze and the number of locked doors are limited. Sounds simple enough, right?


-----Input-----

The first and only line of the input contains a single integer T (1 ≤ T ≤ 10^18), the difficulty of the required maze.


-----Output-----

The first line should contain two integers n and m (1 ≤ n, m ≤ 50) — the number of rows and columns of the maze respectively.

The next line should contain a single integer k (0 ≤ k ≤ 300) — the number of locked doors in the maze.

Then, k lines describing locked doors should follow. Each of them should contain four integers, x_1, y_1, x_2, y_2. This means that the door connecting room (x_1, y_1) and room (x_2, y_2) is locked. Note that room (x_2, y_2) should be adjacent either to the right or to the bottom of (x_1, y_1), i.e. x_2 + y_2 should be equal to x_1 + y_1 + 1. There should not be a locked door that appears twice in the list.

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


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

Output
3 2
0

Input
4

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


-----Note-----

Here are how the sample input and output looks like. The colored arrows denotes all the possible paths while a red cross denotes a locked door.

In the first sample case: [Image] 

In the second sample case: [Image]
user: Thor is getting used to the Earth. As a gift Loki gave him a smartphone. There are n applications on this phone. Thor is fascinated by this phone. He has only one minor issue: he can't count the number of unread notifications generated by those applications (maybe Loki put a curse on it so he can't).

q events are about to happen (in chronological order). They are of three types:  Application x generates a notification (this new notification is unread).  Thor reads all notifications generated so far by application x (he may re-read some notifications).  Thor reads the first t notifications generated by phone applications (notifications generated in first t events of the first type). It's guaranteed that there were at least t events of the first type before this event. Please note that he doesn't read first t unread notifications, he just reads the very first t notifications generated on his phone and he may re-read some of them in this operation. 

Please help Thor and tell him the number of unread notifications after each event. You may assume that initially there are no notifications in the phone.


-----Input-----

The first line of input contains two integers n and q (1 ≤ n, q ≤ 300 000) — the number of applications and the number of events to happen.

The next q lines contain the events. The i-th of these lines starts with an integer type_{i} — type of the i-th event. If type_{i} = 1 or type_{i} = 2 then it is followed by an integer x_{i}. Otherwise it is followed by an integer t_{i} (1 ≤ type_{i} ≤ 3, 1 ≤ x_{i} ≤ n, 1 ≤ t_{i} ≤ q).


-----Output-----

Print the number of unread notifications after each event.


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

Output
1
2
3
2

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

Output
1
2
3
0
1
2



-----Note-----

In the first sample:  Application 3 generates a notification (there is 1 unread notification).  Application 1 generates a notification (there are 2 unread notifications).  Application 2 generates a notification (there are 3 unread notifications).  Thor reads the notification generated by application 3, there are 2 unread notifications left. 

In the second sample test:  Application 2 generates a notification (there is 1 unread notification).  Application 4 generates a notification (there are 2 unread notifications).  Application 2 generates a notification (there are 3 unread notifications).  Thor reads first three notifications and since there are only three of them so far, there will be no unread notification left.  Application 3 generates a notification (there is 1 unread notification).  Application 3 generates a notification (there are 2 unread notifications).
user: Sasha likes programming. Once, during a very long contest, Sasha decided that he was a bit tired and needed to relax. So he did. But since Sasha isn't an ordinary guy, he prefers to relax unusually. During leisure time Sasha likes to upsolve unsolved problems because upsolving is very useful.

Therefore, Sasha decided to upsolve the following problem:

You have an array $a$ with $n$ integers. You need to count the number of funny pairs $(l, r)$ $(l \leq r)$. To check if a pair $(l, r)$ is a funny pair, take $mid = \frac{l + r - 1}{2}$, then if $r - l + 1$ is an even number and $a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} = a_{mid + 1} \oplus a_{mid + 2} \oplus \ldots \oplus a_r$, then the pair is funny. In other words, $\oplus$ of elements of the left half of the subarray from $l$ to $r$ should be equal to $\oplus$ of elements of the right half. Note that $\oplus$ denotes the bitwise XOR operation.

It is time to continue solving the contest, so Sasha asked you to solve this task.


-----Input-----

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^{20}$) — array itself.


-----Output-----

Print one integer — the number of funny pairs. You should consider only pairs where $r - l + 1$ is even number.


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

Output
1

Input
6
3 2 2 3 7 6

Output
3

Input
3
42 4 2

Output
0



-----Note-----

Be as cool as Sasha, upsolve problems!

In the first example, the only funny pair is $(2, 5)$, as $2 \oplus 3 = 4 \oplus 5 = 1$.

In the second example, funny pairs are $(2, 3)$, $(1, 4)$, and $(3, 6)$.

In the third example, there are no funny pairs.
user: This morning Tolik has understood that while he was sleeping he had invented an incredible problem which will be a perfect fit for Codeforces! But, as a "Discuss tasks" project hasn't been born yet (in English, well), he decides to test a problem and asks his uncle.

After a long time thinking, Tolik's uncle hasn't any ideas on how to solve it. But, he doesn't want to tell Tolik about his inability to solve it, so he hasn't found anything better than asking you how to solve this task.

In this task you are given a cell field $n \cdot m$, consisting of $n$ rows and $m$ columns, where point's coordinates $(x, y)$ mean it is situated in the $x$-th row and $y$-th column, considering numeration from one ($1 \leq x \leq n, 1 \leq y \leq m$). Initially, you stand in the cell $(1, 1)$. Every move you can jump from cell $(x, y)$, which you stand in, by any non-zero vector $(dx, dy)$, thus you will stand in the $(x+dx, y+dy)$ cell. Obviously, you can't leave the field, but also there is one more important condition — you're not allowed to use one vector twice. Your task is to visit each cell of the field exactly once (the initial cell is considered as already visited).

Tolik's uncle is a very respectful person. Help him to solve this task!


-----Input-----

The first and only line contains two positive integers $n, m$ ($1 \leq n \cdot m \leq 10^{6}$) — the number of rows and columns of the field respectively.


-----Output-----

Print "-1" (without quotes) if it is impossible to visit every cell exactly once.

Else print $n \cdot m$ pairs of integers, $i$-th from them should contain two integers $x_i, y_i$ ($1 \leq x_i \leq n, 1 \leq y_i \leq m$) — cells of the field in order of visiting, so that all of them are distinct and vectors of jumps between them are distinct too.

Notice that the first cell should have $(1, 1)$ coordinates, according to the statement.


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

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

Output
1 1



-----Note-----

The vectors from the first example in the order of making jumps are $(0, 2), (0, -1), (1, 0), (0, 1), (0, -2)$.
user: Note that the only difference between String Transformation 1 and String Transformation 2 is in the move Koa does. In this version the letter $y$ Koa selects must be strictly greater alphabetically than $x$ (read statement for better understanding). You can make hacks in these problems independently.

Koa the Koala has two strings $A$ and $B$ of the same length $n$ ($|A|=|B|=n$) consisting of the first $20$ lowercase English alphabet letters (ie. from a to t).

In one move Koa:

  selects some subset of positions $p_1, p_2, \ldots, p_k$ ($k \ge 1; 1 \le p_i \le n; p_i \neq p_j$ if $i \neq j$) of $A$ such that $A_{p_1} = A_{p_2} = \ldots = A_{p_k} = x$ (ie. all letters on this positions are equal to some letter $x$).

  selects a letter $y$ (from the first $20$ lowercase letters in English alphabet) such that $y>x$ (ie. letter $y$ is strictly greater alphabetically than $x$).

  sets each letter in positions $p_1, p_2, \ldots, p_k$ to letter $y$. More formally: for each $i$ ($1 \le i \le k$) Koa sets $A_{p_i} = y$.

 Note that you can only modify letters in string $A$.

Koa wants to know the smallest number of moves she has to do to make strings equal to each other ($A = B$) or to determine that there is no way to make them equal. Help her!


-----Input-----

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

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of strings $A$ and $B$.

The second line of each test case contains string $A$ ($|A|=n$).

The third line of each test case contains string $B$ ($|B|=n$).

Both strings consists of the first $20$ lowercase English alphabet letters (ie. from a to t).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case:

Print on a single line the smallest number of moves she has to do to make strings equal to each other ($A = B$) or $-1$ if there is no way to make them equal.


-----Example-----
Input
5
3
aab
bcc
4
cabc
abcb
3
abc
tsr
4
aabd
cccd
5
abcbd
bcdda

Output
2
-1
3
2
-1



-----Note-----  In the $1$-st test case Koa:   selects positions $1$ and $2$ and sets $A_1 = A_2 = $ b ($\color{red}{aa}b \rightarrow \color{blue}{bb}b$).  selects positions $2$ and $3$ and sets $A_2 = A_3 = $ c ($b\color{red}{bb} \rightarrow b\color{blue}{cc}$). 

  In the $2$-nd test case Koa has no way to make string $A$ equal $B$.

  In the $3$-rd test case Koa:   selects position $1$ and sets $A_1 = $ t ($\color{red}{a}bc \rightarrow \color{blue}{t}bc$).  selects position $2$ and sets $A_2 = $ s ($t\color{red}{b}c \rightarrow t\color{blue}{s}c$).  selects position $3$ and sets $A_3 = $ r ($ts\color{red}{c} \rightarrow ts\color{blue}{r}$).
user: You are given a rectangular parallelepiped with sides of positive integer lengths $A$, $B$ and $C$. 

Find the number of different groups of three integers ($a$, $b$, $c$) such that $1\leq a\leq b\leq c$ and parallelepiped $A\times B\times C$ can be paved with parallelepipeds $a\times b\times c$. Note, that all small parallelepipeds have to be rotated in the same direction.

For example, parallelepiped $1\times 5\times 6$ can be divided into parallelepipeds $1\times 3\times 5$, but can not be divided into parallelepipeds $1\times 2\times 3$.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.

Each of the next $t$ lines contains three integers $A$, $B$ and $C$ ($1 \leq A, B, C \leq 10^5$) — the sizes of the parallelepiped.


-----Output-----

For each test case, print the number of different groups of three points that satisfy all given conditions.


-----Example-----
Input
4
1 1 1
1 6 1
2 2 2
100 100 100

Output
1
4
4
165



-----Note-----

In the first test case, rectangular parallelepiped $(1, 1, 1)$ can be only divided into rectangular parallelepiped with sizes $(1, 1, 1)$.

In the second test case, rectangular parallelepiped $(1, 6, 1)$ can be divided into rectangular parallelepipeds with sizes $(1, 1, 1)$, $(1, 1, 2)$, $(1, 1, 3)$ and $(1, 1, 6)$.

In the third test case, rectangular parallelepiped $(2, 2, 2)$ can be divided into rectangular parallelepipeds with sizes $(1, 1, 1)$, $(1, 1, 2)$, $(1, 2, 2)$ and $(2, 2, 2)$.
user: Let $a_1, \ldots, a_n$ be an array of $n$ positive integers. In one operation, you can choose an index $i$ such that $a_i = i$, and remove $a_i$ from the array (after the removal, the remaining parts are concatenated).

The weight of $a$ is defined as the maximum number of elements you can remove.

You must answer $q$ independent queries $(x, y)$: after replacing the $x$ first elements of $a$ and the $y$ last elements of $a$ by $n+1$ (making them impossible to remove), what would be the weight of $a$?


-----Input-----

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 3 \cdot 10^5$)  — the length of the array and the number of queries.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \leq a_i \leq n$) — elements of the array.

The $i$-th of the next $q$ lines contains two integers $x$ and $y$ ($x, y \ge 0$ and $x+y < n$).


-----Output-----

Print $q$ lines, $i$-th line should contain a single integer  — the answer to the $i$-th query.


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

Output
5
11
6
1
0

Input
5 2
1 4 1 2 4
0 0
1 0

Output
2
0



-----Note-----

Explanation of the first query:

After making first $x = 3$ and last $y = 1$ elements impossible to remove, $a$ becomes $[\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times]$ (we represent $14$ as $\times$ for clarity).

Here is a strategy that removes $5$ elements (the element removed is colored in red):  $[\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times]$  $[\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times]$  $[\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times]$  $[\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times]$  $[\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times]$  $[\times, \times, \times, 9, 4, 5, 3, \times]$ (final state) 

It is impossible to remove more than $5$ elements, hence the weight is $5$.
user: There are $n$ football teams in the world. 

The Main Football Organization (MFO) wants to host at most $m$ games. MFO wants the $i$-th game to be played between the teams $a_i$ and $b_i$ in one of the $k$ stadiums. 

Let $s_{ij}$ be the numbers of games the $i$-th team played in the $j$-th stadium. MFO does not want a team to have much more games in one stadium than in the others. Therefore, for each team $i$, the absolute difference between the maximum and minimum among $s_{i1}, s_{i2}, \ldots, s_{ik}$ should not exceed $2$.

Each team has $w_i$ — the amount of money MFO will earn for each game of the $i$-th team. If the $i$-th team plays $l$ games, MFO will earn $w_i \cdot l$.

MFO needs to find what games in what stadiums they need to host in order to earn as much money as possible, not violating the rule they set.

However, this problem is too complicated for MFO. Therefore, they are asking you to help them.


-----Input-----

The first line contains three integers $n$, $m$, $k$ ($3 \leq n \leq 100$, $0 \leq m \leq 1\,000$, $1 \leq k \leq 1\,000$) — the number of teams, the number of games, and the number of stadiums.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \leq w_i \leq 1\,000$) — the amount of money MFO will earn for each game of the $i$-th game.

Each of the following $m$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — the teams that can play the $i$-th game. It is guaranteed that each pair of teams can play at most one game.


-----Output-----

For each game in the same order, print $t_i$ ($1 \leq t_i \leq k$) — the number of the stadium, in which $a_i$ and $b_i$ will play the game. If the $i$-th game should not be played, $t_i$ should be equal to $0$.

If there are multiple answers, print any.


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

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



-----Note-----

One of possible solutions to the example is shown below: [Image]
user: A festival will be held in a town's main street. There are n sections in the main street. The sections are numbered 1 through n from left to right. The distance between each adjacent sections is 1.

In the festival m fireworks will be launched. The i-th (1 ≤ i ≤ m) launching is on time t_{i} at section a_{i}. If you are at section x (1 ≤ x ≤ n) at the time of i-th launching, you'll gain happiness value b_{i} - |a_{i} - x| (note that the happiness value might be a negative value).

You can move up to d length units in a unit time interval, but it's prohibited to go out of the main street. Also you can be in an arbitrary section at initial time moment (time equals to 1), and want to maximize the sum of happiness that can be gained from watching fireworks. Find the maximum total happiness.

Note that two or more fireworks can be launched at the same time.


-----Input-----

The first line contains three integers n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).

Each of the next m lines contains integers a_{i}, b_{i}, t_{i} (1 ≤ a_{i} ≤ n; 1 ≤ b_{i} ≤ 10^9; 1 ≤ t_{i} ≤ 10^9). The i-th line contains description of the i-th launching.

It is guaranteed that the condition t_{i} ≤ t_{i} + 1 (1 ≤ i < m) will be satisfied.


-----Output-----

Print a single integer — the maximum sum of happiness that you can gain from watching all the fireworks.

Please, do not write the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
50 3 1
49 1 1
26 1 4
6 1 10

Output
-31

Input
10 2 1
1 1000 4
9 1000 4

Output
1992
user: Snuke is playing a puzzle game.
In this game, you are given a rectangular board of dimensions R × C, filled with numbers. Each integer i from 1 through N is written twice, at the coordinates (x_{i,1},y_{i,1}) and (x_{i,2},y_{i,2}).
The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from 1 through N.
Here, the curves may not go outside the board or cross each other.
Determine whether this is possible.

-----Constraints-----
 - 1 ≤ R,C ≤ 10^8
 - 1 ≤ N ≤ 10^5
 - 0 ≤ x_{i,1},x_{i,2} ≤ R(1 ≤ i ≤ N)
 - 0 ≤ y_{i,1},y_{i,2} ≤ C(1 ≤ i ≤ N)
 - All given points are distinct.
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
R C N
x_{1,1} y_{1,1} x_{1,2} y_{1,2}
:
x_{N,1} y_{N,1} x_{N,2} y_{N,2}

-----Output-----
Print YES if the objective is achievable; print NO otherwise.

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

-----Sample Output-----
YES


The above figure shows a possible solution.
user: You are given a string S consisting of a,b and c. Find the number of strings that can be possibly obtained by repeatedly performing the following operation zero or more times, modulo 998244353:
 - Choose an integer i such that 1\leq i\leq |S|-1 and the i-th and (i+1)-th characters in S are different. Replace each of the i-th and (i+1)-th characters in S with the character that differs from both of them (among a, b and c).

-----Constraints-----
 - 2 \leq |S| \leq 2 × 10^5
 - S consists of a, b and c.

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

-----Output-----
Print the number of strings that can be possibly obtained by repeatedly performing the operation, modulo 998244353.

-----Sample Input-----
abc

-----Sample Output-----
3

abc, aaa and ccc can be obtained.
user: We have a graph with N vertices and M edges, and there are two people on the graph: Takahashi and Aoki.
The i-th edge connects Vertex U_i and Vertex V_i.
The time it takes to traverse this edge is D_i minutes, regardless of direction and who traverses the edge (Takahashi or Aoki).
Takahashi departs Vertex S and Aoki departs Vertex T at the same time. Takahashi travels to Vertex T and Aoki travels to Vertex S, both in the shortest time possible.
Find the number of the pairs of ways for Takahashi and Aoki to choose their shortest paths such that they never meet (at a vertex or on an edge) during the travel, modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq N \leq 100 000
 - 1 \leq M \leq 200 000
 - 1 \leq S, T \leq N
 - S \neq T
 - 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
 - 1 \leq D_i \leq 10^9 (1 \leq i \leq M)
 - If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j).
 - U_i \neq V_i (1 \leq i \leq M)
 - D_i are integers.
 - The given graph is connected.

-----Input-----
Input is given from Standard Input in the following format:
N M
S T
U_1 V_1 D_1
U_2 V_2 D_2
:
U_M V_M D_M

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

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

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

There are two ways to choose shortest paths that satisfies the condition:
 - Takahashi chooses the path 1 \rightarrow 2 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 4 \rightarrow 1.
 - Takahashi chooses the path 1 \rightarrow 4 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 2 \rightarrow 1.
user: You are given a permutation of 1,2,...,N: p_1,p_2,...,p_N. Determine if the state where p_i=i for every i can be reached by performing the following operation any number of times:
 - Choose three elements p_{i-1},p_{i},p_{i+1} (2\leq i\leq N-1) such that p_{i-1}>p_{i}>p_{i+1} and reverse the order of these three.

-----Constraints-----
 - 3 \leq N \leq 3 × 10^5
 - p_1,p_2,...,p_N is a permutation of 1,2,...,N.

-----Input-----
Input is given from Standard Input in the following format:
N
p_1
:
p_N

-----Output-----
If the state where p_i=i for every i can be reached by performing the operation, print Yes; otherwise, print No.

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

-----Sample Output-----
Yes

The state where p_i=i for every i can be reached as follows:
 - Reverse the order of p_1,p_2,p_3. The sequence p becomes 1,2,5,4,3.
 - Reverse the order of p_3,p_4,p_5. The sequence p becomes 1,2,3,4,5.