meetforever/GRPO_CL huggingface dataset:
user: Everybody knows that the $m$-coder Tournament will happen soon. $m$ schools participate in the tournament, and only one student from each school participates.

There are a total of $n$ students in those schools. Before the tournament, all students put their names and the names of their schools into the Technogoblet of Fire. After that, Technogoblet selects the strongest student from each school to participate. 

Arkady is a hacker who wants to have $k$ Chosen Ones selected by the Technogoblet. Unfortunately, not all of them are the strongest in their schools, but Arkady can make up some new school names and replace some names from Technogoblet with those. You can't use each made-up name more than once. In that case, Technogoblet would select the strongest student in those made-up schools too.

You know the power of each student and schools they study in. Calculate the minimal number of schools Arkady has to make up so that $k$ Chosen Ones would be selected by the Technogoblet.


-----Input-----

The first line contains three integers $n$, $m$ and $k$ ($1 \le n \le 100$, $1 \le m, k \le n$) — the total number of students, the number of schools and the number of the Chosen Ones.

The second line contains $n$ different integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), where $p_i$ denotes the power of $i$-th student. The bigger the power, the stronger the student.

The third line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le m$), where $s_i$ denotes the school the $i$-th student goes to. At least one student studies in each of the schools. 

The fourth line contains $k$ different integers $c_1, c_2, \ldots, c_k$ ($1 \le c_i \le n$)  — the id's of the Chosen Ones.


-----Output-----

Output a single integer  — the minimal number of schools to be made up by Arkady so that $k$ Chosen Ones would be selected by the Technogoblet.


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

Output
1

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

Output
2



-----Note-----

In the first example there's just a single Chosen One with id $3$. His power is equal to $3$, but in the same school $1$, there's a student with id $5$ and power $6$, and that means inaction would not lead to the latter being chosen. If we, however, make up a new school (let its id be $4$) for the Chosen One, Technogoblet would select students with ids $2$ (strongest in $3$), $5$ (strongest in $1$), $6$ (strongest in $2$) and $3$ (strongest in $4$).

In the second example, you can change the school of student $3$ to the made-up $5$ and the school of student $4$ to the made-up $6$. It will cause the Technogoblet to choose students $8$, $7$, $6$, $5$, $3$ and $4$.
user: You are given an array of $n$ integers $a_1$, $a_2$, ..., $a_n$, and a set $b$ of $k$ distinct integers from $1$ to $n$.

In one operation, you may choose two integers $i$ and $x$ ($1 \le i \le n$, $x$ can be any integer) and assign $a_i := x$. This operation can be done only if $i$ does not belong to the set $b$.

Calculate the minimum number of operations you should perform so the array $a$ is increasing (that is, $a_1 < a_2 < a_3 < \dots < a_n$), or report that it is impossible.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$) — the size of the array $a$ and the set $b$, respectively.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$).

Then, if $k \ne 0$, the third line follows, containing $k$ integers $b_1$, $b_2$, ..., $b_k$ ($1 \le b_1 < b_2 < \dots < b_k \le n$). If $k = 0$, this line is skipped.


-----Output-----

If it is impossible to make the array $a$ increasing using the given operations, print $-1$.

Otherwise, print one integer — the minimum number of operations you have to perform.


-----Examples-----
Input
7 2
1 2 1 1 3 5 1
3 5

Output
4

Input
3 3
1 3 2
1 2 3

Output
-1

Input
5 0
4 3 1 2 3

Output
2

Input
10 3
1 3 5 6 12 9 8 10 13 15
2 4 9

Output
3
user: You've been in love with Coronavirus-chan for a long time, but you didn't know where she lived until now. And just now you found out that she lives in a faraway place called Naha. 

You immediately decided to take a vacation and visit Coronavirus-chan. Your vacation lasts exactly $x$ days and that's the exact number of days you will spend visiting your friend. You will spend exactly $x$ consecutive (successive) days visiting Coronavirus-chan.

They use a very unusual calendar in Naha: there are $n$ months in a year, $i$-th month lasts exactly $d_i$ days. Days in the $i$-th month are numbered from $1$ to $d_i$. There are no leap years in Naha.

The mood of Coronavirus-chan (and, accordingly, her desire to hug you) depends on the number of the day in a month. In particular, you get $j$ hugs if you visit Coronavirus-chan on the $j$-th day of the month.

You know about this feature of your friend and want to plan your trip to get as many hugs as possible (and then maybe you can win the heart of Coronavirus-chan). 

Please note that your trip should not necessarily begin and end in the same year.


-----Input-----

The first line of input contains two integers $n$ and $x$ ($1 \le n \le 2 \cdot 10^5$) — the number of months in the year and the number of days you can spend with your friend.

The second line contains $n$ integers $d_1, d_2, \ldots, d_n$, $d_i$ is the number of days in the $i$-th month ($1 \le d_i \le 10^6$).

It is guaranteed that $1 \le x \le d_1 + d_2 + \ldots + d_n$.


-----Output-----

Print one integer — the maximum number of hugs that you can get from Coronavirus-chan during the best vacation in your life.


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

Output
5
Input
3 6
3 3 3

Output
12
Input
5 6
4 2 3 1 3

Output
15


-----Note-----

In the first test case, the numbers of the days in a year are (indices of days in a corresponding month) $\{1,1,2,3,1\}$. Coronavirus-chan will hug you the most if you come on the third day of the year: $2+3=5$ hugs.

In the second test case, the numbers of the days are $\{1,2,3,1,2,3,1,2,3\}$. You will get the most hugs if you arrive on the third day of the year: $3+1+2+3+1+2=12$ hugs.

In the third test case, the numbers of the days are $\{1,2,3,4,1,2, 1,2,3, 1, 1,2,3\}$. You will get the most hugs if you come on the twelfth day of the year: your friend will hug you $2+3+1+2+3+4=15$ times.
user: Eleven wants to choose a new name for herself. As a bunch of geeks, her friends suggested an algorithm to choose a name for her. Eleven wants her name to have exactly n characters.  [Image] 

Her friend suggested that her name should only consist of uppercase and lowercase letters 'O'. More precisely, they suggested that the i-th letter of her name should be 'O' (uppercase) if i is a member of Fibonacci sequence, and 'o' (lowercase) otherwise. The letters in the name are numbered from 1 to n. Fibonacci sequence is the sequence f where  f_1 = 1,  f_2 = 1,  f_{n} = f_{n} - 2 + f_{n} - 1 (n > 2). 

As her friends are too young to know what Fibonacci sequence is, they asked you to help Eleven determine her new name.


-----Input-----

The first and only line of input contains an integer n (1 ≤ n ≤ 1000).


-----Output-----

Print Eleven's new name on the first and only line of output.


-----Examples-----
Input
8

Output
OOOoOooO

Input
15

Output
OOOoOooOooooOoo
user: Naman has two binary strings $s$ and $t$ of length $n$ (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert $s$ into $t$ using the following operation as few times as possible.

In one operation, he can choose any subsequence of $s$ and rotate it clockwise once.

For example, if $s = 1\textbf{1}101\textbf{00}$, he can choose a subsequence corresponding to indices ($1$-based) $\{2, 6, 7 \}$ and rotate them clockwise. The resulting string would then be $s = 1\textbf{0}101\textbf{10}$.

A string $a$ is said to be a subsequence of string $b$ if $a$ can be obtained from $b$ by deleting some characters without changing the ordering of the remaining characters.

To perform a clockwise rotation on a sequence $c$ of size $k$ is to perform an operation which sets $c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$ simultaneously.

Determine the minimum number of operations Naman has to perform to convert $s$ into $t$ or say that it is impossible. 


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 10^6)$ — the length of the strings.

The second line contains the binary string $s$ of length $n$.

The third line contains the binary string $t$ of length $n$.


-----Output-----

If it is impossible to convert $s$ to $t$ after any number of operations, print $-1$.

Otherwise, print the minimum number of operations required.


-----Examples-----
Input
6
010000
000001

Output
1
Input
10
1111100000
0000011111

Output
5
Input
8
10101010
01010101

Output
1
Input
10
1111100000
1111100001

Output
-1


-----Note-----

In the first test, Naman can choose the subsequence corresponding to indices $\{2, 6\}$ and rotate it once to convert $s$ into $t$.

In the second test, he can rotate the subsequence corresponding to all indices $5$ times. It can be proved, that it is the minimum required number of operations.

In the last test, it is impossible to convert $s$ into $t$.
user: A well-known art union called "Kalevich is Alive!" manufactures objects d'art (pictures). The union consists of n painters who decided to organize their work as follows.

Each painter uses only the color that was assigned to him. The colors are distinct for all painters. Let's assume that the first painter uses color 1, the second one uses color 2, and so on. Each picture will contain all these n colors. Adding the j-th color to the i-th picture takes the j-th painter t_{ij} units of time.

Order is important everywhere, so the painters' work is ordered by the following rules:  Each picture is first painted by the first painter, then by the second one, and so on. That is, after the j-th painter finishes working on the picture, it must go to the (j + 1)-th painter (if j < n);  each painter works on the pictures in some order: first, he paints the first picture, then he paints the second picture and so on;  each painter can simultaneously work on at most one picture. However, the painters don't need any time to have a rest;  as soon as the j-th painter finishes his part of working on the picture, the picture immediately becomes available to the next painter. 

Given that the painters start working at time 0, find for each picture the time when it is ready for sale.


-----Input-----

The first line of the input contains integers m, n (1 ≤ m ≤ 50000, 1 ≤ n ≤ 5), where m is the number of pictures and n is the number of painters. Then follow the descriptions of the pictures, one per line. Each line contains n integers t_{i}1, t_{i}2, ..., t_{in} (1 ≤ t_{ij} ≤ 1000), where t_{ij} is the time the j-th painter needs to work on the i-th picture.


-----Output-----

Print the sequence of m integers r_1, r_2, ..., r_{m}, where r_{i} is the moment when the n-th painter stopped working on the i-th picture.


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

Output
1 3 6 10 15 
Input
4 2
2 5
3 1
5 3
10 1

Output
7 8 13 21
user: The academic year has just begun, but lessons and olympiads have already occupied all the free time. It is not a surprise that today Olga fell asleep on the Literature. She had a dream in which she was on a stairs. 

The stairs consists of n steps. The steps are numbered from bottom to top, it means that the lowest step has number 1, and the highest step has number n. Above each of them there is a pointer with the direction (up or down) Olga should move from this step. As soon as Olga goes to the next step, the direction of the pointer (above the step she leaves) changes. It means that the direction "up" changes to "down", the direction "down"  —  to the direction "up".

Olga always moves to the next step in the direction which is shown on the pointer above the step. 

If Olga moves beyond the stairs, she will fall and wake up. Moving beyond the stairs is a moving down from the first step or moving up from the last one (it means the n-th) step. 

In one second Olga moves one step up or down according to the direction of the pointer which is located above the step on which Olga had been at the beginning of the second. 

For each step find the duration of the dream if Olga was at this step at the beginning of the dream.

Olga's fall also takes one second, so if she was on the first step and went down, she would wake up in the next second.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 10^6) — the number of steps on the stairs.

The second line contains a string s with the length n — it denotes the initial direction of pointers on the stairs. The i-th character of string s denotes the direction of the pointer above i-th step, and is either 'U' (it means that this pointer is directed up), or 'D' (it means this pointed is directed down).

The pointers are given in order from bottom to top.


-----Output-----

Print n numbers, the i-th of which is equal either to the duration of Olga's dream or to  - 1 if Olga never goes beyond the stairs, if in the beginning of sleep she was on the i-th step.


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

Output
5 6 3 
Input
10
UUDUDUUDDU

Output
5 12 23 34 36 27 18 11 6 1
user: Seryozha has a very changeable character. This time he refused to leave the room to Dima and his girlfriend (her hame is Inna, by the way). However, the two lovebirds can always find a way to communicate. Today they are writing text messages to each other.

Dima and Inna are using a secret code in their text messages. When Dima wants to send Inna some sentence, he writes out all words, inserting a heart before each word and after the last word. A heart is a sequence of two characters: the "less" characters (<) and the digit three (3). After applying the code, a test message looks like that: <3word_1<3word_2<3 ... word_{n}<3.

Encoding doesn't end here. Then Dima inserts a random number of small English characters, digits, signs "more" and "less" into any places of the message.

Inna knows Dima perfectly well, so she knows what phrase Dima is going to send her beforehand. Inna has just got a text message. Help her find out if Dima encoded the message correctly. In other words, find out if a text message could have been received by encoding in the manner that is described above.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of words in Dima's message. Next n lines contain non-empty words, one word per line. The words only consist of small English letters. The total length of all words doesn't exceed 10^5. 

The last line contains non-empty text message that Inna has got. The number of characters in the text message doesn't exceed 10^5. A text message can contain only small English letters, digits and signs more and less.


-----Output-----

In a single line, print "yes" (without the quotes), if Dima decoded the text message correctly, and "no" (without the quotes) otherwise.


-----Examples-----
Input
3
i
love
you
<3i<3love<23you<3

Output
yes

Input
7
i
am
not
main
in
the
family
<3i<>3am<3the<3<main<3in<3the<3><3family<3

Output
no



-----Note-----

Please note that Dima got a good old kick in the pants for the second sample from the statement.
user: A social network for dogs called DH (DogHouse) has k special servers to recompress uploaded videos of cute cats. After each video is uploaded, it should be recompressed on one (any) of the servers, and only after that it can be saved in the social network.

We know that each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video.

We know the time when each of the n videos were uploaded to the network (in seconds starting from the moment all servers started working). All videos appear at different moments of time and they are recompressed in the order they appear. If some video appeared at time s, then its recompressing can start at that very moment, immediately. Some videos can await recompressing when all the servers are busy. In this case, as soon as a server is available, it immediately starts recompressing another video. The videos that await recompressing go in a queue. If by the moment the videos started being recompressed some servers are available, then any of them starts recompressing the video.

For each video find the moment it stops being recompressed.


-----Input-----

The first line of the input contains integers n and k (1 ≤ n, k ≤ 5·10^5) — the number of videos and servers, respectively.

Next n lines contain the descriptions of the videos as pairs of integers s_{i}, m_{i} (1 ≤ s_{i}, m_{i} ≤ 10^9), where s_{i} is the time in seconds when the i-th video appeared and m_{i} is its duration in minutes. It is guaranteed that all the s_{i}'s are distinct and the videos are given in the chronological order of upload, that is in the order of increasing s_{i}.


-----Output-----

Print n numbers e_1, e_2, ..., e_{n}, where e_{i} is the time in seconds after the servers start working, when the i-th video will be recompressed.


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

Output
6
7
11

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

Output
1000000001
2000000001
3000000001
4000000001
5000000001
5000000004
user: You have to restore the wall. The wall consists of $N$ pillars of bricks, the height of the $i$-th pillar is initially equal to $h_{i}$, the height is measured in number of bricks. After the restoration all the $N$ pillars should have equal heights.

You are allowed the following operations: put a brick on top of one pillar, the cost of this operation is $A$; remove a brick from the top of one non-empty pillar, the cost of this operation is $R$; move a brick from the top of one non-empty pillar to the top of another pillar, the cost of this operation is $M$.

You cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes $0$.

What is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?


-----Input-----

The first line of input contains four integers $N$, $A$, $R$, $M$ ($1 \le N \le 10^{5}$, $0 \le A, R, M \le 10^{4}$) — the number of pillars and the costs of operations.

The second line contains $N$ integers $h_{i}$ ($0 \le h_{i} \le 10^{9}$) — initial heights of pillars.


-----Output-----

Print one integer — the minimal cost of restoration.


-----Examples-----
Input
3 1 100 100
1 3 8

Output
12

Input
3 100 1 100
1 3 8

Output
9

Input
3 100 100 1
1 3 8

Output
4

Input
5 1 2 4
5 5 3 6 5

Output
4

Input
5 1 2 2
5 5 3 6 5

Output
3
user: Petya and Gena love playing table tennis. A single match is played according to the following rules: a match consists of multiple sets, each set consists of multiple serves. Each serve is won by one of the players, this player scores one point. As soon as one of the players scores t points, he wins the set; then the next set starts and scores of both players are being set to 0. As soon as one of the players wins the total of s sets, he wins the match and the match is over. Here s and t are some positive integer numbers.

To spice it up, Petya and Gena choose new numbers s and t before every match. Besides, for the sake of history they keep a record of each match: that is, for each serve they write down the winner. Serve winners are recorded in the chronological order. In a record the set is over as soon as one of the players scores t points and the match is over as soon as one of the players wins s sets.

Petya and Gena have found a record of an old match. Unfortunately, the sequence of serves in the record isn't divided into sets and numbers s and t for the given match are also lost. The players now wonder what values of s and t might be. Can you determine all the possible options?


-----Input-----

The first line contains a single integer n — the length of the sequence of games (1 ≤ n ≤ 10^5).

The second line contains n space-separated integers a_{i}. If a_{i} = 1, then the i-th serve was won by Petya, if a_{i} = 2, then the i-th serve was won by Gena.

It is not guaranteed that at least one option for numbers s and t corresponds to the given record.


-----Output-----

In the first line print a single number k — the number of options for numbers s and t.

In each of the following k lines print two integers s_{i} and t_{i} — the option for numbers s and t. Print the options in the order of increasing s_{i}, and for equal s_{i} — in the order of increasing t_{i}.


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

Output
2
1 3
3 1

Input
4
1 1 1 1

Output
3
1 4
2 2
4 1

Input
4
1 2 1 2

Output
0

Input
8
2 1 2 1 1 1 1 1

Output
3
1 6
2 3
6 1
user: Vasily the bear has got a sequence of positive integers a_1, a_2, ..., a_{n}. Vasily the Bear wants to write out several numbers on a piece of paper so that the beauty of the numbers he wrote out was maximum. 

The beauty of the written out numbers b_1, b_2, ..., b_{k} is such maximum non-negative integer v, that number b_1 and b_2 and ... and b_{k} is divisible by number 2^{v} without a remainder. If such number v doesn't exist (that is, for any non-negative integer v, number b_1 and b_2 and ... and b_{k} is divisible by 2^{v} without a remainder), the beauty of the written out numbers equals -1. 

Tell the bear which numbers he should write out so that the beauty of the written out numbers is maximum. If there are multiple ways to write out the numbers, you need to choose the one where the bear writes out as many numbers as possible.

Here expression x and y means applying the bitwise AND operation to numbers x and y. In programming languages C++ and Java this operation is represented by "&", in Pascal — by "and".


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_1 < a_2 < ... < a_{n} ≤ 10^9).


-----Output-----

In the first line print a single integer k (k > 0), showing how many numbers to write out. In the second line print k integers b_1, b_2, ..., b_{k} — the numbers to write out. You are allowed to print numbers b_1, b_2, ..., b_{k} in any order, but all of them must be distinct. If there are multiple ways to write out the numbers, choose the one with the maximum number of numbers to write out. If there still are multiple ways, you are allowed to print any of them.


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

Output
2
4 5

Input
3
1 2 4

Output
1
4
user: Sereja and Dima play a game. The rules of the game are very simple. The players have n cards in a row. Each card contains a number, all numbers on the cards are distinct. The players take turns, Sereja moves first. During his turn a player can take one card: either the leftmost card in a row, or the rightmost one. The game ends when there is no more cards. The player who has the maximum sum of numbers on his cards by the end of the game, wins.

Sereja and Dima are being greedy. Each of them chooses the card with the larger number during his move.

Inna is a friend of Sereja and Dima. She knows which strategy the guys are using, so she wants to determine the final score, given the initial state of the game. Help her.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of cards on the table. The second line contains space-separated numbers on the cards from left to right. The numbers on the cards are distinct integers from 1 to 1000.


-----Output-----

On a single line, print two integers. The first number is the number of Sereja's points at the end of the game, the second number is the number of Dima's points at the end of the game.


-----Examples-----
Input
4
4 1 2 10

Output
12 5

Input
7
1 2 3 4 5 6 7

Output
16 12



-----Note-----

In the first sample Sereja will take cards with numbers 10 and 2, so Sereja's sum is 12. Dima will take cards with numbers 4 and 1, so Dima's sum is 5.