meetforever/GRPO_CL huggingface dataset:
user: There are two popular keyboard layouts in Berland, they differ only in letters positions. All the other keys are the same. In Berland they use alphabet with 26 letters which coincides with English alphabet.

You are given two strings consisting of 26 distinct letters each: all keys of the first and the second layouts in the same order. 

You are also given some text consisting of small and capital English letters and digits. It is known that it was typed in the first layout, but the writer intended to type it in the second layout. Print the text if the same keys were pressed in the second layout.

Since all keys but letters are the same in both layouts, the capitalization of the letters should remain the same, as well as all other characters.


-----Input-----

The first line contains a string of length 26 consisting of distinct lowercase English letters. This is the first layout.

The second line contains a string of length 26 consisting of distinct lowercase English letters. This is the second layout.

The third line contains a non-empty string s consisting of lowercase and uppercase English letters and digits. This is the text typed in the first layout. The length of s does not exceed 1000.


-----Output-----

Print the text if the same keys were pressed in the second layout.


-----Examples-----
Input
qwertyuiopasdfghjklzxcvbnm
veamhjsgqocnrbfxdtwkylupzi
TwccpQZAvb2017

Output
HelloVKCup2017

Input
mnbvcxzlkjhgfdsapoiuytrewq
asdfghjklqwertyuiopzxcvbnm
7abaCABAABAcaba7

Output
7uduGUDUUDUgudu7
user: Eugeny has array a = a_1, a_2, ..., a_{n}, consisting of n integers. Each integer a_{i} equals to -1, or to 1. Also, he has m queries:  Query number i is given as a pair of integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n).  The response to the query will be integer 1, if the elements of array a can be rearranged so as the sum a_{l}_{i} + a_{l}_{i} + 1 + ... + a_{r}_{i} = 0, otherwise the response to the query will be integer 0. 

Help Eugeny, answer all his queries.


-----Input-----

The first line contains integers n and m (1 ≤ n, m ≤ 2·10^5). The second line contains n integers a_1, a_2, ..., a_{n} (a_{i} = -1, 1). Next m lines contain Eugene's queries. The i-th line contains integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n).


-----Output-----

Print m integers — the responses to Eugene's queries in the order they occur in the input.


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

Output
0
1
0

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

Output
0
1
0
1
0
user: В самолёте есть n рядов мест. Если смотреть на ряды сверху, то в каждом ряду есть 3 места слева, затем проход между рядами, затем 4 центральных места, затем ещё один проход между рядами, а затем ещё 3 места справа.

Известно, что некоторые места уже заняты пассажирами. Всего есть два вида пассажиров — статусные (те, которые часто летают) и обычные. 

Перед вами стоит задача рассадить ещё k обычных пассажиров так, чтобы суммарное число соседей у статусных пассажиров было минимально возможным. Два пассажира считаются соседями, если они сидят в одном ряду и между ними нет других мест и прохода между рядами. Если пассажир является соседним пассажиром для двух статусных пассажиров, то его следует учитывать в сумме соседей дважды.


-----Входные данные-----

В первой строке следуют два целых числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10·n) — количество рядов мест в самолёте и количество пассажиров, которых нужно рассадить.

Далее следует описание рядов мест самолёта по одному ряду в строке. Если очередной символ равен '-', то это проход между рядами. Если очередной символ равен '.', то это свободное место. Если очередной символ равен 'S', то на текущем месте будет сидеть статусный пассажир. Если очередной символ равен 'P', то на текущем месте будет сидеть обычный пассажир. 

Гарантируется, что количество свободных мест не меньше k. Гарантируется, что все ряды удовлетворяют описанному в условии формату.


-----Выходные данные-----

В первую строку выведите минимальное суммарное число соседей у статусных пассажиров.

Далее выведите план рассадки пассажиров, который минимизирует суммарное количество соседей у статусных пассажиров, в том же формате, что и во входных данных. Если в свободное место нужно посадить одного из k пассажиров, выведите строчную букву 'x' вместо символа '.'. 


-----Примеры-----
Входные данные
1 2
SP.-SS.S-S.S

Выходные данные
5
SPx-SSxS-S.S

Входные данные
4 9
PP.-PPPS-S.S
PSP-PPSP-.S.
.S.-S..P-SS.
P.S-P.PP-PSP

Выходные данные
15
PPx-PPPS-S.S
PSP-PPSP-xSx
xSx-SxxP-SSx
P.S-PxPP-PSP



-----Примечание-----

В первом примере нужно посадить ещё двух обычных пассажиров. Для минимизации соседей у статусных пассажиров, нужно посадить первого из них на третье слева место, а второго на любое из оставшихся двух мест, так как независимо от выбора места он станет соседом двух статусных пассажиров. 

Изначально, у статусного пассажира, который сидит на самом левом месте уже есть сосед. Также на четвёртом и пятом местах слева сидят статусные пассажиры, являющиеся соседями друг для друга (что добавляет к сумме 2).

Таким образом, после посадки ещё двух обычных пассажиров, итоговое суммарное количество соседей у статусных пассажиров станет равно пяти.
user: The Greatest Secret Ever consists of n words, indexed by positive integers from 1 to n. The secret needs dividing between k Keepers (let's index them by positive integers from 1 to k), the i-th Keeper gets a non-empty set of words with numbers from the set U_{i} = (u_{i}, 1, u_{i}, 2, ..., u_{i}, |U_{i}|). Here and below we'll presuppose that the set elements are written in the increasing order.

We'll say that the secret is safe if the following conditions are hold:  for any two indexes i, j (1 ≤ i < j ≤ k) the intersection of sets U_{i} and U_{j} is an empty set;  the union of sets U_1, U_2, ..., U_{k} is set (1, 2, ..., n);  in each set U_{i}, its elements u_{i}, 1, u_{i}, 2, ..., u_{i}, |U_{i}| do not form an arithmetic progression (in particular, |U_{i}| ≥ 3 should hold). 

Let us remind you that the elements of set (u_1, u_2, ..., u_{s}) form an arithmetic progression if there is such number d, that for all i (1 ≤ i < s) fulfills u_{i} + d = u_{i} + 1. For example, the elements of sets (5), (1, 10) and (1, 5, 9) form arithmetic progressions and the elements of sets (1, 2, 4) and (3, 6, 8) don't.

Your task is to find any partition of the set of words into subsets U_1, U_2, ..., U_{k} so that the secret is safe. Otherwise indicate that there's no such partition.


-----Input-----

The input consists of a single line which contains two integers n and k (2 ≤ k ≤ n ≤ 10^6) — the number of words in the secret and the number of the Keepers. The numbers are separated by a single space.


-----Output-----

If there is no way to keep the secret safe, print a single integer "-1" (without the quotes). Otherwise, print n integers, the i-th of them representing the number of the Keeper who's got the i-th word of the secret.

If there are multiple solutions, print any of them.


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

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

Input
5 2

Output
-1
user: It's been almost a week since Polycarp couldn't get rid of insomnia. And as you may already know, one week in Berland lasts k days!

When Polycarp went to a doctor with his problem, the doctor asked him about his sleeping schedule (more specifically, the average amount of hours of sleep per week). Luckily, Polycarp kept records of sleep times for the last n days. So now he has a sequence a_1, a_2, ..., a_{n}, where a_{i} is the sleep time on the i-th day.

The number of records is so large that Polycarp is unable to calculate the average value by himself. Thus he is asking you to help him with the calculations. To get the average Polycarp is going to consider k consecutive days as a week. So there will be n - k + 1 weeks to take into consideration. For example, if k = 2, n = 3 and a = [3, 4, 7], then the result is $\frac{(3 + 4) +(4 + 7)}{2} = 9$.

You should write a program which will calculate average sleep times of Polycarp over all weeks.


-----Input-----

The first line contains two integer numbers n and k (1 ≤ k ≤ n ≤ 2·10^5).

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----Output-----

Output average sleeping time over all weeks. 

The answer is considered to be correct if its absolute or relative error does not exceed 10^{ - 6}. In particular, it is enough to output real number with at least 6 digits after the decimal point.


-----Examples-----
Input
3 2
3 4 7

Output
9.0000000000

Input
1 1
10

Output
10.0000000000

Input
8 2
1 2 4 100000 123 456 789 1

Output
28964.2857142857



-----Note-----

In the third example there are n - k + 1 = 7 weeks, so the answer is sums of all weeks divided by 7.
user: There are n piles of pebbles on the table, the i-th pile contains a_{i} pebbles. Your task is to paint each pebble using one of the k given colors so that for each color c and any two piles i and j the difference between the number of pebbles of color c in pile i and number of pebbles of color c in pile j is at most one.

In other words, let's say that b_{i}, c is the number of pebbles of color c in the i-th pile. Then for any 1 ≤ c ≤ k, 1 ≤ i, j ≤ n the following condition must be satisfied |b_{i}, c - b_{j}, c| ≤ 1. It isn't necessary to use all k colors: if color c hasn't been used in pile i, then b_{i}, c is considered to be zero.


-----Input-----

The first line of the input contains positive integers n and k (1 ≤ n, k ≤ 100), separated by a space — the number of piles and the number of colors respectively.

The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100) denoting number of pebbles in each of the piles.


-----Output-----

If there is no way to paint the pebbles satisfying the given condition, output "NO" (without quotes) .

Otherwise in the first line output "YES" (without quotes). Then n lines should follow, the i-th of them should contain a_{i} space-separated integers. j-th (1 ≤ j ≤ a_{i}) of these integers should be equal to the color of the j-th pebble in the i-th pile. If there are several possible answers, you may output any of them.


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

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

Input
5 2
3 2 4 1 3

Output
NO

Input
5 4
3 2 4 3 5

Output
YES
1 2 3
1 3
1 2 3 4
1 3 4
1 1 2 3 4
user: Vasya became interested in bioinformatics. He's going to write an article about similar cyclic DNA sequences, so he invented a new method for determining the similarity of cyclic sequences.

Let's assume that strings s and t have the same length n, then the function h(s, t) is defined as the number of positions in which the respective symbols of s and t are the same. Function h(s, t) can be used to define the function of Vasya distance ρ(s, t): $\rho(s, t) = \sum_{i = 0}^{n - 1} \sum_{j = 0}^{n - 1} h(\operatorname{shift}(s, i), \operatorname{shift}(t, j))$ where $\operatorname{shift}(s, i)$ is obtained from string s, by applying left circular shift i times. For example, ρ("AGC", "CGT") =  h("AGC", "CGT") + h("AGC", "GTC") + h("AGC", "TCG") +  h("GCA", "CGT") + h("GCA", "GTC") + h("GCA", "TCG") +  h("CAG", "CGT") + h("CAG", "GTC") + h("CAG", "TCG") =  1 + 1 + 0 + 0 + 1 + 1 + 1 + 0 + 1 = 6

Vasya found a string s of length n on the Internet. Now he wants to count how many strings t there are such that the Vasya distance from the string s attains maximum possible value. Formally speaking, t must satisfy the equation: $\rho(s, t) = \operatorname{max}_{u :|u|=|s|} \rho(s, u)$.

Vasya could not try all possible strings to find an answer, so he needs your help. As the answer may be very large, count the number of such strings modulo 10^9 + 7.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 10^5).

The second line of the input contains a single string of length n, consisting of characters "ACGT".


-----Output-----

Print a single number — the answer modulo 10^9 + 7.


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

Output
1

Input
2
AG

Output
4

Input
3
TTT

Output
1



-----Note-----

Please note that if for two distinct strings t_1 and t_2 values ρ(s, t_1) и ρ(s, t_2) are maximum among all possible t, then both strings must be taken into account in the answer even if one of them can be obtained by a circular shift of another one.

In the first sample, there is ρ("C", "C") = 1, for the remaining strings t of length 1 the value of ρ(s, t) is 0.

In the second sample, ρ("AG", "AG") = ρ("AG", "GA") = ρ("AG", "AA") = ρ("AG", "GG") = 4.

In the third sample, ρ("TTT", "TTT") = 27
user: Leonid wants to become a glass carver (the person who creates beautiful artworks by cutting the glass). He already has a rectangular w mm  ×  h mm sheet of glass, a diamond glass cutter and lots of enthusiasm. What he lacks is understanding of what to carve and how.

In order not to waste time, he decided to practice the technique of carving. To do this, he makes vertical and horizontal cuts through the entire sheet. This process results in making smaller rectangular fragments of glass. Leonid does not move the newly made glass fragments. In particular, a cut divides each fragment of glass that it goes through into smaller fragments.

After each cut Leonid tries to determine what area the largest of the currently available glass fragments has. Since there appear more and more fragments, this question takes him more and more time and distracts him from the fascinating process.

Leonid offers to divide the labor — he will cut glass, and you will calculate the area of the maximum fragment after each cut. Do you agree?


-----Input-----

The first line contains three integers w, h, n (2 ≤ w, h ≤ 200 000, 1 ≤ n ≤ 200 000).

Next n lines contain the descriptions of the cuts. Each description has the form H y or V x. In the first case Leonid makes the horizontal cut at the distance y millimeters (1 ≤ y ≤ h - 1) from the lower edge of the original sheet of glass. In the second case Leonid makes a vertical cut at distance x (1 ≤ x ≤ w - 1) millimeters from the left edge of the original sheet of glass. It is guaranteed that Leonid won't make two identical cuts.


-----Output-----

After each cut print on a single line the area of the maximum available glass fragment in mm^2.


-----Examples-----
Input
4 3 4
H 2
V 2
V 3
V 1

Output
8
4
4
2

Input
7 6 5
H 4
V 3
V 5
H 2
V 1

Output
28
16
12
6
4



-----Note-----

Picture for the first sample test:  [Image]  Picture for the second sample test:  $\square$
user: The Fair Nut found a string $s$. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences $p_1, p_2, \ldots, p_k$, such that:   For each $i$ ($1 \leq i \leq k$), $s_{p_i} =$ 'a'.  For each $i$ ($1 \leq i < k$), there is such $j$ that $p_i < j < p_{i + 1}$ and $s_j =$ 'b'. 

The Nut is upset because he doesn't know how to find the number. Help him.

This number should be calculated modulo $10^9 + 7$.


-----Input-----

The first line contains the string $s$ ($1 \leq |s| \leq 10^5$) consisting of lowercase Latin letters.


-----Output-----

In a single line print the answer to the problem — the number of such sequences $p_1, p_2, \ldots, p_k$ modulo $10^9 + 7$.


-----Examples-----
Input
abbaa

Output
5
Input
baaaa

Output
4
Input
agaa

Output
3


-----Note-----

In the first example, there are $5$ possible sequences. $[1]$, $[4]$, $[5]$, $[1, 4]$, $[1, 5]$.

In the second example, there are $4$ possible sequences. $[2]$, $[3]$, $[4]$, $[5]$.

In the third example, there are $3$ possible sequences. $[1]$, $[3]$, $[4]$.
user: Takahashi has two integers X and Y.
He computed X + Y and X - Y, and the results were A and B, respectively.
Now he cannot remember what X and Y were. Find X and Y for him.

-----Constraints-----
 - -100 \leq A, B \leq 100
 - For the given integers A and B, there uniquely exist integers X and Y such that X + Y = A and X - Y = B.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Print X and Y.

-----Sample Input-----
2 -2

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

If X = 0 and Y = 2, they match the situation: 0 + 2 = 2 and 0 - 2 = -2.
user: There are two 100-story buildings, called A and B. (In this problem, the ground floor is called the first floor.)
For each i = 1,\dots, 100, the i-th floor of A and that of B are connected by a corridor.
Also, for each i = 1,\dots, 99, there is a corridor that connects the (i+1)-th floor of A and the i-th floor of B.
You can traverse each of those corridors in both directions, and it takes you x minutes to get to the other end.
Additionally, both of the buildings have staircases. For each i = 1,\dots, 99, a staircase connects the i-th and (i+1)-th floors of a building, and you need y minutes to get to an adjacent floor by taking the stairs.
Find the minimum time needed to reach the b-th floor of B from the a-th floor of A.

-----Constraints-----
 - 1 \leq a,b,x,y \leq 100
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
a b x y

-----Output-----
Print the minimum time needed to reach the b-th floor of B from the a-th floor of A.

-----Sample Input-----
2 1 1 5

-----Sample Output-----
1

There is a corridor that directly connects the 2-nd floor of A and the 1-st floor of B, so you can travel between them in 1 minute.
This is the fastest way to get there, since taking the stairs just once costs you 5 minutes.
user: Arkady's morning seemed to be straight of his nightmare. He overslept through the whole morning and, still half-asleep, got into the tram that arrived the first. Some time after, leaving the tram, he realized that he was not sure about the line number of the tram he was in.

During his ride, Arkady woke up several times and each time he saw the tram stopping at some stop. For each stop he knows which lines of tram stop there. Given this information, can you help Arkady determine what are the possible lines of the tram he was in?


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 100$) — the number of stops Arkady saw.

The next $n$ lines describe the stops. Each of them starts with a single integer $r$ ($1 \le r \le 100$) — the number of tram lines that stop there. $r$ distinct integers follow, each one between $1$ and $100$, inclusive, — the line numbers. They can be in arbitrary order.

It is guaranteed that Arkady's information is consistent, i.e. there is at least one tram line that Arkady could take.


-----Output-----

Print all tram lines that Arkady could be in, in arbitrary order.


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

Output
1 4 

Input
5
1 1
10 10 9 8 7 100 5 4 3 99 1
5 1 2 3 4 5
5 4 1 3 2 5
4 10 1 5 3

Output
1 



-----Note-----

Consider the first example. Arkady woke up three times. The first time he saw a stop with lines $1$, $4$, $6$. The second time he saw a stop with lines $1$, $4$. The third time he saw a stop with lines $10$, $5$, $6$, $4$ and $1$. He can be in a tram of one of two lines: $1$ or $4$.
user: You will receive 5 points for solving this problem.

Manao has invented a new operation on strings that is called folding. Each fold happens between a pair of consecutive letters and places the second part of the string above first part, running in the opposite direction and aligned to the position of the fold. Using this operation, Manao converts the string into a structure that has one more level than there were fold operations performed. See the following examples for clarity.

We will denote the positions of folds with '|' characters. For example, the word "ABRACADABRA" written as "AB|RACA|DAB|RA" indicates that it has been folded three times: first, between the leftmost pair of 'B' and 'R' letters; second, between 'A' and 'D'; and third, between the rightmost pair of 'B' and 'R' letters. Here are several examples of folded strings:

"ABCDEF|GHIJK" |  "A|BCDEFGHIJK" |  "AB|RACA|DAB|RA" |  "X|XXXXX|X|X|XXXXXX"

               |                 |                   |       XXXXXX

    KJIHG      |   KJIHGFEDCB    |      AR           |       X

   ABCDEF      |            A    |     DAB           |       X

               |                 |     ACAR          |       XXXXX

               |                 |       AB          |           X



One last example for "ABCD|EFGH|IJ|K": 

 K

IJ

HGFE

ABCD



Manao noticed that each folded string can be viewed as several piles of letters. For instance, in the previous example, there are four piles, which can be read as "AHI", "BGJK", "CF", and "DE" from bottom to top. Manao wonders what is the highest pile of identical letters he can build using fold operations on a given word. Note that the pile should not contain gaps and should start at the bottom level. For example, in the rightmost of the four examples above, none of the piles would be considered valid since each of them has gaps, starts above the bottom level, or both.


-----Input-----

The input will consist of one line containing a single string of n characters with 1 ≤ n ≤ 1000 and no spaces. All characters of the string will be uppercase letters.

This problem doesn't have subproblems. You will get 5 points for the correct submission.


-----Output-----

Print a single integer — the size of the largest pile composed of identical characters that can be seen in a valid result of folding operations on the given string.


-----Examples-----
Input
ABRACADABRA

Output
3

Input
ABBBCBDB

Output
3

Input
AB

Output
1



-----Note-----

Consider the first example. Manao can create a pile of three 'A's using the folding "AB|RACAD|ABRA", which results in the following structure: 

ABRA

DACAR

   AB



In the second example, Manao can create a pile of three 'B's using the following folding: "AB|BB|CBDB". 

CBDB

BB

AB



Another way for Manao to create a pile of three 'B's with "ABBBCBDB" is the following folding: "AB|B|BCBDB". 

 BCBDB

 B

AB



In the third example, there are no folds performed and the string is just written in one line.
user: You are given a rooted tree on $n$ vertices, its root is the vertex number $1$. The $i$-th vertex contains a number $w_i$. Split it into the minimum possible number of vertical paths in such a way that each path contains no more than $L$ vertices and the sum of integers $w_i$ on each path does not exceed $S$. Each vertex should belong to exactly one path.

A vertical path is a sequence of vertices $v_1, v_2, \ldots, v_k$ where $v_i$ ($i \ge 2$) is the parent of $v_{i - 1}$.


-----Input-----

The first line contains three integers $n$, $L$, $S$ ($1 \le n \le 10^5$, $1 \le L \le 10^5$, $1 \le S \le 10^{18}$) — the number of vertices, the maximum number of vertices in one path and the maximum sum in one path.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10^9$) — the numbers in the vertices of the tree.

The third line contains $n - 1$ integers $p_2, \ldots, p_n$ ($1 \le p_i < i$), where $p_i$ is the parent of the $i$-th vertex in the tree.


-----Output-----

Output one number  — the minimum number of vertical paths. If it is impossible to split the tree, output $-1$.


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

Output
3
Input
3 3 6
1 2 3
1 1

Output
2
Input
1 1 10000
10001

Output
-1


-----Note-----

In the first sample the tree is split into $\{1\},\ \{2\},\ \{3\}$.

In the second sample the tree is split into $\{1,\ 2\},\ \{3\}$ or $\{1,\ 3\},\ \{2\}$.

In the third sample it is impossible to split the tree.