meetforever/GRPO_CL huggingface dataset:
user: Vasya had an array of $n$ integers, each element of the array was from $1$ to $n$. He chose $m$ pairs of different positions and wrote them down to a sheet of paper. Then Vasya compared the elements at these positions, and wrote down the results of the comparisons to another sheet of paper. For each pair he wrote either "greater", "less", or "equal".

After several years, he has found the first sheet of paper, but he couldn't find the second one. Also he doesn't remember the array he had. In particular, he doesn't remember if the array had equal elements. He has told this sad story to his informatics teacher Dr Helen.

She told him that it could be the case that even if Vasya finds his second sheet, he would still not be able to find out whether the array had two equal elements. 

Now Vasya wants to find two arrays of integers, each of length $n$. All elements of the first array must be distinct, and there must be two equal elements in the second array. For each pair of positions Vasya wrote at the first sheet of paper, the result of the comparison must be the same for the corresponding elements of the first array, and the corresponding elements of the second array. 

Help Vasya find two such arrays of length $n$, or find out that there are no such arrays for his sets of pairs.


-----Input-----

The first line of input contains two integers $n$, $m$ — the number of elements in the array and number of comparisons made by Vasya ($1 \le n \le 100\,000$, $0 \le m \le 100\,000$).

Each of the following $m$ lines contains two integers $a_i$, $b_i$  — the positions of the $i$-th comparison ($1 \le a_i, b_i \le n$; $a_i \ne b_i$). It's guaranteed that any unordered pair is given in the input at most once.


-----Output-----

The first line of output must contain "YES" if there exist two arrays, such that the results of comparisons would be the same, and all numbers in the first one are distinct, and the second one contains two equal numbers. Otherwise it must contain "NO".

If the arrays exist, the second line must contain the array of distinct integers, the third line must contain the array, that contains at least one pair of equal elements. Elements of the arrays must be integers from $1$ to $n$.


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

Output
NO

Input
3 1
1 2

Output
YES
1 3 2 
1 3 1 

Input
4 3
1 2
1 3
2 4

Output
YES
1 3 4 2 
1 3 4 1
user: Graph constructive problems are back! This time the graph you are asked to build should match the following properties.

The graph is connected if and only if there exists a path between every pair of vertices.

The diameter (aka "longest shortest path") of a connected undirected graph is the maximum number of edges in the shortest path between any pair of its vertices.

The degree of a vertex is the number of edges incident to it.

Given a sequence of $n$ integers $a_1, a_2, \dots, a_n$ construct a connected undirected graph of $n$ vertices such that:  the graph contains no self-loops and no multiple edges;  the degree $d_i$ of the $i$-th vertex doesn't exceed $a_i$ (i.e. $d_i \le a_i$);  the diameter of the graph is maximum possible. 

Output the resulting graph or report that no solution exists.


-----Input-----

The first line contains a single integer $n$ ($3 \le n \le 500$) — the number of vertices in the graph.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n - 1$) — the upper limits to vertex degrees.


-----Output-----

Print "NO" if no graph can be constructed under the given conditions.

Otherwise print "YES" and the diameter of the resulting graph in the first line.

The second line should contain a single integer $m$ — the number of edges in the resulting graph.

The $i$-th of the next $m$ lines should contain two integers $v_i, u_i$ ($1 \le v_i, u_i \le n$, $v_i \neq u_i$) — the description of the $i$-th edge. The graph should contain no multiple edges — for each pair $(x, y)$ you output, you should output no more pairs $(x, y)$ or $(y, x)$.


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

Output
YES 2
2
1 2
2 3

Input
5
1 4 1 1 1

Output
YES 2
4
1 2
3 2
4 2
5 2

Input
3
1 1 1

Output
NO



-----Note-----

Here are the graphs for the first two example cases. Both have diameter of $2$. [Image] $d_1 = 1 \le a_1 = 2$

$d_2 = 2 \le a_2 = 2$

$d_3 = 1 \le a_3 = 2$  [Image] $d_1 = 1 \le a_1 = 1$

$d_2 = 4 \le a_2 = 4$

$d_3 = 1 \le a_3 = 1$

$d_4 = 1 \le a_4 = 1$
user: You are given a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ and an integer $k$, such that $1 \leq k \leq n$. A permutation means that every number from $1$ to $n$ is contained in $p$ exactly once.

Let's consider all partitions of this permutation into $k$ disjoint segments. Formally, a partition is a set of segments $\{[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]\}$, such that:

  $1 \leq l_i \leq r_i \leq n$ for all $1 \leq i \leq k$;  For all $1 \leq j \leq n$ there exists exactly one segment $[l_i, r_i]$, such that $l_i \leq j \leq r_i$. 

Two partitions are different if there exists a segment that lies in one partition but not the other.

Let's calculate the partition value, defined as $\sum\limits_{i=1}^{k} {\max\limits_{l_i \leq j \leq r_i} {p_j}}$, for all possible partitions of the permutation into $k$ disjoint segments. Find the maximum possible partition value over all such partitions, and the number of partitions with this value. As the second value can be very large, you should find its remainder when divided by $998\,244\,353$.


-----Input-----

The first line contains two integers, $n$ and $k$ ($1 \leq k \leq n \leq 200\,000$) — the size of the given permutation and the number of segments in a partition.

The second line contains $n$ different integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$) — the given permutation.


-----Output-----

Print two integers — the maximum possible partition value over all partitions of the permutation into $k$ disjoint segments and the number of such partitions for which the partition value is equal to the maximum possible value, modulo $998\,244\,353$.

Please note that you should only find the second value modulo $998\,244\,353$.


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

Output
5 2

Input
5 5
2 1 5 3 4

Output
15 1

Input
7 3
2 7 3 1 5 4 6

Output
18 6



-----Note-----

In the first test, for $k = 2$, there exists only two valid partitions: $\{[1, 1], [2, 3]\}$ and $\{[1, 2], [3, 3]\}$. For each partition, the partition value is equal to $2 + 3 = 5$. So, the maximum possible value is $5$ and the number of partitions is $2$.

In the third test, for $k = 3$, the partitions with the maximum possible partition value are $\{[1, 2], [3, 5], [6, 7]\}$, $\{[1, 3], [4, 5], [6, 7]\}$, $\{[1, 4], [5, 5], [6, 7]\}$, $\{[1, 2], [3, 6], [7, 7]\}$, $\{[1, 3], [4, 6], [7, 7]\}$, $\{[1, 4], [5, 6], [7, 7]\}$. For all of them, the partition value is equal to $7 + 5 + 6 = 18$. 

The partition $\{[1, 2], [3, 4], [5, 7]\}$, however, has the partition value $7 + 3 + 6 = 16$. This is not the maximum possible value, so we don't count it.
user: One unknown hacker wants to get the admin's password of AtForces testing system, to get problems from the next contest. To achieve that, he sneaked into the administrator's office and stole a piece of paper with a list of $n$ passwords — strings, consists of small Latin letters.

Hacker went home and started preparing to hack AtForces. He found that the system contains only passwords from the stolen list and that the system determines the equivalence of the passwords $a$ and $b$ as follows:  two passwords $a$ and $b$ are equivalent if there is a letter, that exists in both $a$ and $b$;  two passwords $a$ and $b$ are equivalent if there is a password $c$ from the list, which is equivalent to both $a$ and $b$. 

If a password is set in the system and an equivalent one is applied to access the system, then the user is accessed into the system.

For example, if the list contain passwords "a", "b", "ab", "d", then passwords "a", "b", "ab" are equivalent to each other, but the password "d" is not equivalent to any other password from list. In other words, if:  admin's password is "b", then you can access to system by using any of this passwords: "a", "b", "ab";  admin's password is "d", then you can access to system by using only "d". 

Only one password from the list is the admin's password from the testing system. Help hacker to calculate the minimal number of passwords, required to guaranteed access to the system. Keep in mind that the hacker does not know which password is set in the system.


-----Input-----

The first line contain integer $n$ ($1 \le n \le 2 \cdot 10^5$) — number of passwords in the list. Next $n$ lines contains passwords from the list – non-empty strings $s_i$, with length at most $50$ letters. Some of the passwords may be equal.

It is guaranteed that the total length of all passwords does not exceed $10^6$ letters. All of them consist only of lowercase Latin letters.


-----Output-----

In a single line print the minimal number of passwords, the use of which will allow guaranteed to access the system.


-----Examples-----
Input
4
a
b
ab
d

Output
2
Input
3
ab
bc
abc

Output
1
Input
1
codeforces

Output
1


-----Note-----

In the second example hacker need to use any of the passwords to access the system.
user: The city park of IT City contains n east to west paths and n north to south paths. Each east to west path crosses each north to south path, so there are n^2 intersections.

The city funded purchase of five benches. To make it seems that there are many benches it was decided to place them on as many paths as possible. Obviously this requirement is satisfied by the following scheme: each bench is placed on a cross of paths and each path contains not more than one bench.

Help the park administration count the number of ways to place the benches.


-----Input-----

The only line of the input contains one integer n (5 ≤ n ≤ 100) — the number of east to west paths and north to south paths.


-----Output-----

Output one integer — the number of ways to place the benches.


-----Examples-----
Input
5

Output
120
user: Find out if it is possible to partition the first $n$ positive integers into two non-empty disjoint sets $S_1$ and $S_2$ such that:$\mathrm{gcd}(\mathrm{sum}(S_1), \mathrm{sum}(S_2)) > 1$ 

Here $\mathrm{sum}(S)$ denotes the sum of all elements present in set $S$ and $\mathrm{gcd}$ means thegreatest common divisor.

Every integer number from $1$ to $n$ should be present in exactly one of $S_1$ or $S_2$.


-----Input-----

The only line of the input contains a single integer $n$ ($1 \le n \le 45\,000$)


-----Output-----

If such partition doesn't exist, print "No" (quotes for clarity).

Otherwise, print "Yes" (quotes for clarity), followed by two lines, describing $S_1$ and $S_2$ respectively.

Each set description starts with the set size, followed by the elements of the set in any order. Each set must be non-empty.

If there are multiple possible partitions — print any of them.


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

Output
No
Input
3

Output
Yes
1 2
2 1 3 



-----Note-----

In the first example, there is no way to partition a single number into two non-empty sets, hence the answer is "No".

In the second example, the sums of the sets are $2$ and $4$ respectively. The $\mathrm{gcd}(2, 4) = 2 > 1$, hence that is one of the possible answers.
user: You are given an integer number $n$. The following algorithm is applied to it:

  if $n = 0$, then end algorithm;  find the smallest prime divisor $d$ of $n$;  subtract $d$ from $n$ and go to step $1$. 

Determine the number of subtrations the algorithm will make.


-----Input-----

The only line contains a single integer $n$ ($2 \le n \le 10^{10}$).


-----Output-----

Print a single integer — the number of subtractions the algorithm will make.


-----Examples-----
Input
5

Output
1

Input
4

Output
2



-----Note-----

In the first example $5$ is the smallest prime divisor, thus it gets subtracted right away to make a $0$.

In the second example $2$ is the smallest prime divisor at both steps.
user: The numbers of all offices in the new building of the Tax Office of IT City will have lucky numbers.

Lucky number is a number that consists of digits 7 and 8 only. Find the maximum number of offices in the new building of the Tax Office given that a door-plate can hold a number not longer than n digits.


-----Input-----

The only line of input contains one integer n (1 ≤ n ≤ 55) — the maximum length of a number that a door-plate can hold.


-----Output-----

Output one integer — the maximum number of offices, than can have unique lucky numbers not longer than n digits.


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

Output
6
user: Bees Alice and Alesya gave beekeeper Polina famous card game "Set" as a Christmas present. The deck consists of cards that vary in four features across three options for each kind of feature: number of shapes, shape, shading, and color. In this game, some combinations of three cards are said to make up a set. For every feature — color, number, shape, and shading — the three cards must display that feature as either all the same, or pairwise different. The picture below shows how sets look.

[Image]

Polina came up with a new game called "Hyperset". In her game, there are $n$ cards with $k$ features, each feature has three possible values: "S", "E", or "T". The original "Set" game can be viewed as "Hyperset" with $k = 4$.

Similarly to the original game, three cards form a set, if all features are the same for all cards or are pairwise different. The goal of the game is to compute the number of ways to choose three cards that form a set.

Unfortunately, winter holidays have come to an end, and it's time for Polina to go to school. Help Polina find the number of sets among the cards lying on the table.


-----Input-----

The first line of each test contains two integers $n$ and $k$ ($1 \le n \le 1500$, $1 \le k \le 30$) — number of cards and number of features.

Each of the following $n$ lines contains a card description: a string consisting of $k$ letters "S", "E", "T". The $i$-th character of this string decribes the $i$-th feature of that card. All cards are distinct.


-----Output-----

Output a single integer — the number of ways to choose three cards that form a set.


-----Examples-----
Input
3 3
SET
ETS
TSE

Output
1
Input
3 4
SETE
ETSE
TSES

Output
0
Input
5 4
SETT
TEST
EEET
ESTE
STES

Output
2


-----Note-----

In the third example test, these two triples of cards are sets:  "SETT", "TEST", "EEET"  "TEST", "ESTE", "STES"
user: Andryusha is an orderly boy and likes to keep things in their place.

Today he faced a problem to put his socks in the wardrobe. He has n distinct pairs of socks which are initially in a bag. The pairs are numbered from 1 to n. Andryusha wants to put paired socks together and put them in the wardrobe. He takes the socks one by one from the bag, and for each sock he looks whether the pair of this sock has been already took out of the bag, or not. If not (that means the pair of this sock is still in the bag), he puts the current socks on the table in front of him. Otherwise, he puts both socks from the pair to the wardrobe.

Andryusha remembers the order in which he took the socks from the bag. Can you tell him what is the maximum number of socks that were on the table at the same time? 


-----Input-----

The first line contains the single integer n (1 ≤ n ≤ 10^5) — the number of sock pairs.

The second line contains 2n integers x_1, x_2, ..., x_2n (1 ≤ x_{i} ≤ n), which describe the order in which Andryusha took the socks from the bag. More precisely, x_{i} means that the i-th sock Andryusha took out was from pair x_{i}.

It is guaranteed that Andryusha took exactly two socks of each pair.


-----Output-----

Print single integer — the maximum number of socks that were on the table at the same time.


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

Output
1

Input
3
2 1 1 3 2 3

Output
2



-----Note-----

In the first example Andryusha took a sock from the first pair and put it on the table. Then he took the next sock which is from the first pair as well, so he immediately puts both socks to the wardrobe. Thus, at most one sock was on the table at the same time.

In the second example Andryusha behaved as follows:   Initially the table was empty, he took out a sock from pair 2 and put it on the table.  Sock (2) was on the table. Andryusha took out a sock from pair 1 and put it on the table.  Socks (1, 2) were on the table. Andryusha took out a sock from pair 1, and put this pair into the wardrobe.  Sock (2) was on the table. Andryusha took out a sock from pair 3 and put it on the table.  Socks (2, 3) were on the table. Andryusha took out a sock from pair 2, and put this pair into the wardrobe.  Sock (3) was on the table. Andryusha took out a sock from pair 3 and put this pair into the wardrobe.  Thus, at most two socks were on the table at the same time.
user: The Bitlandians are quite weird people. They have very peculiar customs.

As is customary, Uncle J. wants to have n eggs painted for Bitruz (an ancient Bitland festival). He has asked G. and A. to do the work.

The kids are excited because just as is customary, they're going to be paid for the job! 

Overall uncle J. has got n eggs. G. named his price for painting each egg. Similarly, A. named his price for painting each egg. It turns out that for each egg the sum of the money both A. and G. want for the painting equals 1000.

Uncle J. wants to distribute the eggs between the children so as to give each egg to exactly one child. Also, Uncle J. wants the total money paid to A. to be different from the total money paid to G. by no more than 500.

Help Uncle J. Find the required distribution of eggs or otherwise say that distributing the eggs in the required manner is impossible.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^6) — the number of eggs.

Next n lines contain two integers a_{i} and g_{i} each (0 ≤ a_{i}, g_{i} ≤ 1000; a_{i} + g_{i} = 1000): a_{i} is the price said by A. for the i-th egg and g_{i} is the price said by G. for the i-th egg.


-----Output-----

If it is impossible to assign the painting, print "-1" (without quotes).

Otherwise print a string, consisting of n letters "G" and "A". The i-th letter of this string should represent the child who will get the i-th egg in the required distribution. Letter "A" represents A. and letter "G" represents G. If we denote the money Uncle J. must pay A. for the painting as S_{a}, and the money Uncle J. must pay G. for the painting as S_{g}, then this inequality must hold: |S_{a}  -  S_{g}|  ≤  500. 

If there are several solutions, you are allowed to print any of them.


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

Output
AG

Input
3
400 600
400 600
400 600

Output
AGA
user: A magic island Geraldion, where Gerald lives, has its own currency system. It uses banknotes of several values. But the problem is, the system is not perfect and sometimes it happens that Geraldionians cannot express a certain sum of money with any set of banknotes. Of course, they can use any number of banknotes of each value. Such sum is called unfortunate. Gerald wondered: what is the minimum unfortunate sum?


-----Input-----

The first line contains number n (1 ≤ n ≤ 1000) — the number of values of the banknotes that used in Geraldion. 

The second line contains n distinct space-separated numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) — the values of the banknotes.


-----Output-----

Print a single line — the minimum unfortunate sum. If there are no unfortunate sums, print  - 1.


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

Output
-1
user: In this problem your goal is to sort an array consisting of n integers in at most n swaps. For the given array find the sequence of swaps that makes the array sorted in the non-descending order. Swaps are performed consecutively, one after another.

Note that in this problem you do not have to minimize the number of swaps — your task is to find any sequence that is no longer than n.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 3000) — the number of array elements. The second line contains elements of array: a_0, a_1, ..., a_{n} - 1 ( - 10^9 ≤ a_{i} ≤ 10^9), where a_{i} is the i-th element of the array. The elements are numerated from 0 to n - 1 from left to right. Some integers may appear in the array more than once.


-----Output-----

In the first line print k (0 ≤ k ≤ n) — the number of swaps. Next k lines must contain the descriptions of the k swaps, one per line. Each swap should be printed as a pair of integers i, j (0 ≤ i, j ≤ n - 1), representing the swap of elements a_{i} and a_{j}. You can print indices in the pairs in any order. The swaps are performed in the order they appear in the output, from the first to the last. It is allowed to print i = j and swap the same pair of elements multiple times.

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


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

Output
2
0 3
4 2

Input
6
10 20 20 40 60 60

Output
0

Input
2
101 100

Output
1
0 1
user: You are given an integer $n$.

You should find a list of pairs $(x_1, y_1)$, $(x_2, y_2)$, ..., $(x_q, y_q)$ ($1 \leq x_i, y_i \leq n$) satisfying the following condition.

Let's consider some function $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ (we define $\mathbb{N}$ as the set of positive integers). In other words, $f$ is a function that returns a positive integer for a pair of positive integers.

Let's make an array $a_1, a_2, \ldots, a_n$, where $a_i = i$ initially.

You will perform $q$ operations, in $i$-th of them you will:   assign $t = f(a_{x_i}, a_{y_i})$ ($t$ is a temporary variable, it is used only for the next two assignments);  assign $a_{x_i} = t$;  assign $a_{y_i} = t$. 

In other words, you need to simultaneously change $a_{x_i}$ and $a_{y_i}$ to $f(a_{x_i}, a_{y_i})$. Note that during this process $f(p, q)$ is always the same for a fixed pair of $p$ and $q$.

In the end, there should be at most two different numbers in the array $a$.

It should be true for any function $f$.

Find any possible list of pairs. The number of pairs should not exceed $5 \cdot 10^5$.


-----Input-----

The single line contains a single integer $n$ ($1 \leq n \leq 15\,000$).


-----Output-----

In the first line print $q$ ($0 \leq q \leq 5 \cdot 10^5$) — the number of pairs.

In each of the next $q$ lines print two integers. In the $i$-th line print $x_i$, $y_i$ ($1 \leq x_i, y_i \leq n$).

The condition described in the statement should be satisfied.

If there exists multiple answers you can print any of them.


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

Output
1
1 2

Input
4

Output
2
1 2
3 4



-----Note-----

In the first example, after performing the only operation the array $a$ will be $[f(a_1, a_2), f(a_1, a_2), a_3]$. It will always have at most two different numbers.

In the second example, after performing two operations the array $a$ will be $[f(a_1, a_2), f(a_1, a_2), f(a_3, a_4), f(a_3, a_4)]$. It will always have at most two different numbers.
user: Amr has got a large array of size n. Amr doesn't like large arrays so he intends to make it smaller.

Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.

Help Amr by choosing the smallest subsegment possible.


-----Input-----

The first line contains one number n (1 ≤ n ≤ 10^5), the size of the array.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6), representing elements of the array.


-----Output-----

Output two integers l, r (1 ≤ l ≤ r ≤ n), the beginning and the end of the subsegment chosen respectively.

If there are several possible answers you may output any of them. 


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

Output
1 5
Input
5
1 2 2 3 1

Output
2 3
Input
6
1 2 2 1 1 2

Output
1 5


-----Note-----

A subsegment B of an array A from l to r is an array of size r - l + 1 where B_{i} = A_{l} + i - 1 for all 1 ≤ i ≤ r - l + 1