meetforever/GRPO_CL huggingface dataset:
user: Sometimes it is not easy to come to an agreement in a bargain. Right now Sasha and Vova can't come to an agreement: Sasha names a price as high as possible, then Vova wants to remove as many digits from the price as possible. In more details, Sasha names some integer price $n$, Vova removes a non-empty substring of (consecutive) digits from the price, the remaining digits close the gap, and the resulting integer is the price.

For example, is Sasha names $1213121$, Vova can remove the substring $1312$, and the result is $121$.

It is allowed for result to contain leading zeros. If Vova removes all digits, the price is considered to be $0$.

Sasha wants to come up with some constraints so that Vova can't just remove all digits, but he needs some arguments supporting the constraints. To start with, he wants to compute the sum of all possible resulting prices after Vova's move.

Help Sasha to compute this sum. Since the answer can be very large, print it modulo $10^9 + 7$.


-----Input-----

The first and only line contains a single integer $n$ ($1 \le n < 10^{10^5}$).


-----Output-----

In the only line print the required sum modulo $10^9 + 7$.


-----Examples-----
Input
107

Output
42

Input
100500100500

Output
428101984



-----Note-----

Consider the first example.

Vova can choose to remove $1$, $0$, $7$, $10$, $07$, or $107$. The results are $07$, $17$, $10$, $7$, $1$, $0$. Their sum is $42$.
user: Let's analyze a program written on some strange programming language. The variables in this language have names consisting of $1$ to $4$ characters, and each character is a lowercase or an uppercase Latin letter, or a digit. There is an extra constraint that the first character should not be a digit.

There are four types of operations in the program, each denoted by one of the characters: $, ^, # or &.

Each line of the program has one of the following formats:   <lvalue>=<rvalue>, where <lvalue> and <rvalue> are valid variable names;  <lvalue>=<arg1><op><arg2>, where <lvalue>, <arg1> and <arg2> are valid variable names, and <op> is an operation character. 

The program is executed line-by-line, and the result of execution is stored in a variable having the name res. If res is never assigned in the program, then the result will be equal to the value of res before running the program.

Two programs are called equivalent if no matter which operations do characters $, ^, # and & denote (but, obviously, performing the same operation on the same arguments gives the same result) and which values do variables have before execution of program, the value of res after running the first program is equal to the value of res after running the second program (the programs are executed independently).

You are given a program consisting of $n$ lines. Your task is to write a program consisting of minimum possible number of lines that is equivalent to the program you are given.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 1000$) — the number of lines in the program.

Then $n$ lines follow — the program itself. Each line corresponds to the format described in the statement and has no extra whitespaces.


-----Output-----

In the first line print $k$ — the minimum number of lines in the equivalent program.

Then print $k$ lines without any whitespaces — an equivalent program having exactly $k$ lines, in the same format it is described in the statement.


-----Examples-----
Input
4
c=aa#bb
d12=c
res=c^d12
tmp=aa$c

Output
2
aaaa=aa#bb
res=aaaa^aaaa

Input
2
max=aaaa$bbbb
min=bbbb^aaaa

Output
0
user: You are given a tree consisting of $n$ nodes. You want to write some labels on the tree's edges such that the following conditions hold:

  Every label is an integer between $0$ and $n-2$ inclusive.  All the written labels are distinct.  The largest value among $MEX(u,v)$ over all pairs of nodes $(u,v)$ is as small as possible. 

Here, $MEX(u,v)$ denotes the smallest non-negative integer that isn't written on any edge on the unique simple path from node $u$ to node $v$.


-----Input-----

The first line contains the integer $n$ ($2 \le n \le 10^5$) — the number of nodes in the tree.

Each of the next $n-1$ lines contains two space-separated integers $u$ and $v$ ($1 \le u,v \le n$) that mean there's an edge between nodes $u$ and $v$. It's guaranteed that the given graph is a tree.


-----Output-----

Output $n-1$ integers. The $i^{th}$ of them will be the number written on the $i^{th}$ edge (in the input order).


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

Output
0
1

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

Output
0
3
2
4
1


-----Note-----

The tree from the second sample:

[Image]
user: Petya and Vasya are tossing a coin. Their friend Valera is appointed as a judge. The game is very simple. First Vasya tosses a coin x times, then Petya tosses a coin y times. If the tossing player gets head, he scores one point. If he gets tail, nobody gets any points. The winner is the player with most points by the end of the game. If boys have the same number of points, the game finishes with a draw.

At some point, Valera lost his count, and so he can not say exactly what the score is at the end of the game. But there are things he remembers for sure. He remembers that the entire game Vasya got heads at least a times, and Petya got heads at least b times. Moreover, he knows that the winner of the game was Vasya. Valera wants to use this information to know every possible outcome of the game, which do not contradict his memories.


-----Input-----

The single line contains four integers x, y, a, b (1 ≤ a ≤ x ≤ 100, 1 ≤ b ≤ y ≤ 100). The numbers on the line are separated by a space.


-----Output-----

In the first line print integer n — the number of possible outcomes of the game. Then on n lines print the outcomes. On the i-th line print a space-separated pair of integers c_{i}, d_{i} — the number of heads Vasya and Petya got in the i-th outcome of the game, correspondingly. Print pairs of integers (c_{i}, d_{i}) in the strictly increasing order.

Let us remind you that the pair of numbers (p_1, q_1) is less than the pair of numbers (p_2, q_2), if p_1 < p_2, or p_1 = p_2 and also q_1 < q_2.


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

Output
3
2 1
3 1
3 2

Input
2 4 2 2

Output
0
user: For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations.

Max is a young biologist. For $n$ days he watched a specific shark, and now he knows the distance the shark traveled in each of the days. All the distances are distinct. Max wants to know now how many locations the shark visited. He assumed there is such an integer $k$ that if the shark in some day traveled the distance strictly less than $k$, then it didn't change the location; otherwise, if in one day the shark traveled the distance greater than or equal to $k$; then it was changing a location in that day. Note that it is possible that the shark changed a location for several consecutive days, in each of them the shark traveled the distance at least $k$.

The shark never returned to the same location after it has moved from it. Thus, in the sequence of $n$ days we can find consecutive nonempty segments when the shark traveled the distance less than $k$ in each of the days: each such segment corresponds to one location. Max wants to choose such $k$ that the lengths of all such segments are equal.

Find such integer $k$, that the number of locations is as large as possible. If there are several such $k$, print the smallest one.


-----Input-----

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

The second line contains $n$ distinct positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the distance traveled in each of the day.


-----Output-----

Print a single integer $k$, such that   the shark was in each location the same number of days,  the number of locations is maximum possible satisfying the first condition,  $k$ is smallest possible satisfying the first and second conditions. 


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

Output
7
Input
6
25 1 2 3 14 36

Output
2


-----Note-----

In the first example the shark travels inside a location on days $1$ and $2$ (first location), then on $4$-th and $5$-th days (second location), then on $7$-th and $8$-th days (third location). There are three locations in total.

In the second example the shark only moves inside a location on the $2$-nd day, so there is only one location.
user: A PIN code is a string that consists of exactly $4$ digits. Examples of possible PIN codes: 7013, 0000 and 0990. Please note that the PIN code can begin with any digit, even with 0.

Polycarp has $n$ ($2 \le n \le 10$) bank cards, the PIN code of the $i$-th card is $p_i$.

Polycarp has recently read a recommendation that it is better to set different PIN codes on different cards. Thus he wants to change the minimal number of digits in the PIN codes of his cards so that all $n$ codes would become different.

Formally, in one step, Polycarp picks $i$-th card ($1 \le i \le n$), then in its PIN code $p_i$ selects one position (from $1$ to $4$), and changes the digit in this position to any other. He needs to change the minimum number of digits so that all PIN codes become different.

Polycarp quickly solved this problem. Can you solve it?


-----Input-----

The first line contains integer $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then test cases follow.

The first line of each of $t$ test sets contains a single integer $n$ ($2 \le n \le 10$) — the number of Polycarp's bank cards. The next $n$ lines contain the PIN codes $p_1, p_2, \dots, p_n$ — one per line. The length of each of them is $4$. All PIN codes consist of digits only.


-----Output-----

Print the answers to $t$ test sets. The answer to each set should consist of a $n + 1$ lines

In the first line print $k$ — the least number of changes to make all PIN codes different. In the next $n$ lines output the changed PIN codes in the order corresponding to their appearance in the input. If there are several optimal answers, print any of them.


-----Example-----
Input
3
2
1234
0600
2
1337
1337
4
3139
3139
3139
3139

Output
0
1234
0600
1
1337
1237
3
3139
3138
3939
6139
user: Vasya has started watching football games. He has learned that for some fouls the players receive yellow cards, and for some fouls they receive red cards. A player who receives the second yellow card automatically receives a red card.

Vasya is watching a recorded football match now and makes notes of all the fouls that he would give a card for. Help Vasya determine all the moments in time when players would be given red cards if Vasya were the judge. For each player, Vasya wants to know only the first moment of time when he would receive a red card from Vasya.


-----Input-----

The first line contains the name of the team playing at home. The second line contains the name of the team playing away. Both lines are not empty. The lengths of both lines do not exceed 20. Each line contains only of large English letters. The names of the teams are distinct.

Next follows number n (1 ≤ n ≤ 90) — the number of fouls. 

Each of the following n lines contains information about a foul in the following form:   first goes number t (1 ≤ t ≤ 90) — the minute when the foul occurs;  then goes letter "h" or letter "a" — if the letter is "h", then the card was given to a home team player, otherwise the card was given to an away team player;  then goes the player's number m (1 ≤ m ≤ 99);  then goes letter "y" or letter "r" — if the letter is "y", that means that the yellow card was given, otherwise the red card was given. 

The players from different teams can have the same number. The players within one team have distinct numbers. The fouls go chronologically, no two fouls happened at the same minute.


-----Output-----

For each event when a player received his first red card in a chronological order print a string containing the following information:  The name of the team to which the player belongs;  the player's number in his team;  the minute when he received the card. 

If no player received a card, then you do not need to print anything.

It is possible case that the program will not print anything to the output (if there were no red cards).


-----Examples-----
Input
MC
CSKA
9
28 a 3 y
62 h 25 y
66 h 42 y
70 h 25 y
77 a 4 y
79 a 25 y
82 h 42 r
89 h 16 y
90 a 13 r

Output
MC 25 70
MC 42 82
CSKA 13 90
user: In the school computer room there are n servers which are responsible for processing several computing tasks. You know the number of scheduled tasks for each server: there are m_{i} tasks assigned to the i-th server.

In order to balance the load for each server, you want to reassign some tasks to make the difference between the most loaded server and the least loaded server as small as possible. In other words you want to minimize expression m_{a} - m_{b}, where a is the most loaded server and b is the least loaded one.

In one second you can reassign a single task. Thus in one second you can choose any pair of servers and move a single task from one server to another.

Write a program to find the minimum number of seconds needed to balance the load of servers.


-----Input-----

The first line contains positive number n (1 ≤ n ≤ 10^5) — the number of the servers. 

The second line contains the sequence of non-negative integers m_1, m_2, ..., m_{n} (0 ≤ m_{i} ≤ 2·10^4), where m_{i} is the number of tasks assigned to the i-th server.


-----Output-----

Print the minimum number of seconds required to balance the load.


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

Output
2

Input
7
10 11 10 11 10 11 11

Output
0

Input
5
1 2 3 4 5

Output
3



-----Note-----

In the first example two seconds are needed. In each second, a single task from server #2 should be moved to server #1. After two seconds there should be 3 tasks on server #1 and 4 tasks on server #2.

In the second example the load is already balanced.

A possible sequence of task movements for the third example is:  move a task from server #4 to server #1 (the sequence m becomes: 2 2 3 3 5);  then move task from server #5 to server #1 (the sequence m becomes: 3 2 3 3 4);  then move task from server #5 to server #2 (the sequence m becomes: 3 3 3 3 3). 

The above sequence is one of several possible ways to balance the load of servers in three seconds.
user: Mad scientist Mike entertains himself by arranging rows of dominoes. He doesn't need dominoes, though: he uses rectangular magnets instead. Each magnet has two poles, positive (a "plus") and negative (a "minus"). If two magnets are put together at a close distance, then the like poles will repel each other and the opposite poles will attract each other.

Mike starts by laying one magnet horizontally on the table. During each following step Mike adds one more magnet horizontally to the right end of the row. Depending on how Mike puts the magnet on the table, it is either attracted to the previous one (forming a group of multiple magnets linked together) or repelled by it (then Mike lays this magnet at some distance to the right from the previous one). We assume that a sole magnet not linked to others forms a group of its own. [Image] 

Mike arranged multiple magnets in a row. Determine the number of groups that the magnets formed.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 100000) — the number of magnets. Then n lines follow. The i-th line (1 ≤ i ≤ n) contains either characters "01", if Mike put the i-th magnet in the "plus-minus" position, or characters "10", if Mike put the magnet in the "minus-plus" position.


-----Output-----

On the single line of the output print the number of groups of magnets.


-----Examples-----
Input
6
10
10
10
01
10
10

Output
3

Input
4
01
01
10
10

Output
2



-----Note-----

The first testcase corresponds to the figure. The testcase has three groups consisting of three, one and two magnets.

The second testcase has two groups, each consisting of two magnets.
user: Let's call beauty of an array $b_1, b_2, \ldots, b_n$ ($n > 1$)  — $\min\limits_{1 \leq i < j \leq n} |b_i - b_j|$.

You're given an array $a_1, a_2, \ldots a_n$ and a number $k$. Calculate the sum of beauty over all subsequences of the array of length exactly $k$. As this number can be very large, output it modulo $998244353$.

A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements.


-----Input-----

The first line contains integers $n, k$ ($2 \le k \le n \le 1000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^5$).


-----Output-----

Output one integer — the sum of beauty over all subsequences of the array of length exactly $k$. As this number can be very large, output it modulo $998244353$.


-----Examples-----
Input
4 3
1 7 3 5

Output
8
Input
5 5
1 10 100 1000 10000

Output
9


-----Note-----

In the first example, there are $4$ subsequences of length $3$ — $[1, 7, 3]$, $[1, 3, 5]$, $[7, 3, 5]$, $[1, 7, 5]$, each of which has beauty $2$, so answer is $8$.

In the second example, there is only one subsequence of length $5$ — the whole array, which has the beauty equal to $|10-1| = 9$.
user: You are playing a new famous fighting game: Kortal Mombat XII. You have to perform a brutality on your opponent's character.

You are playing the game on the new generation console so your gamepad have $26$ buttons. Each button has a single lowercase Latin letter from 'a' to 'z' written on it. All the letters on buttons are pairwise distinct.

You are given a sequence of hits, the $i$-th hit deals $a_i$ units of damage to the opponent's character. To perform the $i$-th hit you have to press the button $s_i$ on your gamepad. Hits are numbered from $1$ to $n$.

You know that if you press some button more than $k$ times in a row then it'll break. You cherish your gamepad and don't want to break any of its buttons.

To perform a brutality you have to land some of the hits of the given sequence. You are allowed to skip any of them, however changing the initial order of the sequence is prohibited. The total damage dealt is the sum of $a_i$ over all $i$ for the hits which weren't skipped.

Note that if you skip the hit then the counter of consecutive presses the button won't reset.

Your task is to skip some hits to deal the maximum possible total damage to the opponent's character and not break your gamepad buttons.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of hits and the maximum number of times you can push the same button 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 the damage of the $i$-th hit.

The third line of the input contains the string $s$ consisting of exactly $n$ lowercase Latin letters — the sequence of hits (each character is the letter on the button you need to press to perform the corresponding hit).


-----Output-----

Print one integer $dmg$ — the maximum possible damage to the opponent's character you can deal without breaking your gamepad buttons.


-----Examples-----
Input
7 3
1 5 16 18 7 2 10
baaaaca

Output
54

Input
5 5
2 4 1 3 1000
aaaaa

Output
1010

Input
5 4
2 4 1 3 1000
aaaaa

Output
1009

Input
8 1
10 15 2 1 4 8 15 16
qqwweerr

Output
41

Input
6 3
14 18 9 19 2 15
cccccc

Output
52

Input
2 1
10 10
qq

Output
10



-----Note-----

In the first example you can choose hits with numbers $[1, 3, 4, 5, 6, 7]$ with the total damage $1 + 16 + 18 + 7 + 2 + 10 = 54$.

In the second example you can choose all hits so the total damage is $2 + 4 + 1 + 3 + 1000 = 1010$.

In the third example you can choose all hits expect the third one so the total damage is $2 + 4 + 3 + 1000 = 1009$.

In the fourth example you can choose hits with numbers $[2, 3, 6, 8]$. Only this way you can reach the maximum total damage $15 + 2 + 8 + 16 = 41$.

In the fifth example you can choose only hits with numbers $[2, 4, 6]$ with the total damage $18 + 19 + 15 = 52$.

In the sixth example you can change either first hit or the second hit (it does not matter) with the total damage $10$.
user: Consider a football tournament where n teams participate. Each team has two football kits: for home games, and for away games. The kit for home games of the i-th team has color x_{i} and the kit for away games of this team has color y_{i} (x_{i} ≠ y_{i}).

In the tournament, each team plays exactly one home game and exactly one away game with each other team (n(n - 1) games in total). The team, that plays the home game, traditionally plays in its home kit. The team that plays an away game plays in its away kit. However, if two teams has the kits of the same color, they cannot be distinguished. In this case the away team plays in its home kit.

Calculate how many games in the described tournament each team plays in its home kit and how many games it plays in its away kit.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of teams. Next n lines contain the description of the teams. The i-th line contains two space-separated numbers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ 10^5; x_{i} ≠ y_{i}) — the color numbers for the home and away kits of the i-th team.


-----Output-----

For each team, print on a single line two space-separated integers — the number of games this team is going to play in home and away kits, correspondingly. Print the answers for the teams in the order they appeared in the input.


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

Output
2 0
2 0

Input
3
1 2
2 1
1 3

Output
3 1
4 0
2 2