meetforever/GRPO_CL huggingface dataset:
user: Hiasat registered a new account in NeckoForces and when his friends found out about that, each one of them asked to use his name as Hiasat's handle.

Luckily for Hiasat, he can change his handle in some points in time. Also he knows the exact moments friends will visit his profile page. Formally, you are given a sequence of events of two types:

  $1$ — Hiasat can change his handle.  $2$ $s$ — friend $s$ visits Hiasat's profile. 

The friend $s$ will be happy, if each time he visits Hiasat's profile his handle would be $s$.

Hiasat asks you to help him, find the maximum possible number of happy friends he can get.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5, 1 \le m \le 40$) — the number of events and the number of friends.

Then $n$ lines follow, each denoting an event of one of two types:   $1$ — Hiasat can change his handle.  $2$ $s$ — friend $s$ ($1 \le |s| \le 40$) visits Hiasat's profile. 

It's guaranteed, that each friend's name consists only of lowercase Latin letters.

It's guaranteed, that the first event is always of the first type and each friend will visit Hiasat's profile at least once.


-----Output-----

Print a single integer — the maximum number of happy friends.


-----Examples-----
Input
5 3
1
2 motarack
2 mike
1
2 light

Output
2

Input
4 3
1
2 alice
2 bob
2 tanyaromanova

Output
1



-----Note-----

In the first example, the best way is to change the handle to the "motarack" in the first event and to the "light" in the fourth event. This way, "motarack" and "light" will be happy, but "mike" will not.

In the second example, you can choose either "alice", "bob" or "tanyaromanova" and only that friend will be happy.
user: After a probationary period in the game development company of IT City Petya was included in a group of the programmers that develops a new turn-based strategy game resembling the well known "Heroes of Might & Magic". A part of the game is turn-based fights of big squadrons of enemies on infinite fields where every cell is in form of a hexagon.

Some of magic effects are able to affect several field cells at once, cells that are situated not farther than n cells away from the cell in which the effect was applied. The distance between cells is the minimum number of cell border crosses on a path from one cell to another.

It is easy to see that the number of cells affected by a magic effect grows rapidly when n increases, so it can adversely affect the game performance. That's why Petya decided to write a program that can, given n, determine the number of cells that should be repainted after effect application, so that game designers can balance scale of the effects and the game performance. Help him to do it. Find the number of hexagons situated not farther than n cells away from a given cell. [Image] 


-----Input-----

The only line of the input contains one integer n (0 ≤ n ≤ 10^9).


-----Output-----

Output one integer — the number of hexagons situated not farther than n cells away from a given cell.


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

Output
19
user: When Sasha was studying in the seventh grade, he started listening to music a lot. In order to evaluate which songs he likes more, he introduced the notion of the song's prettiness. The title of the song is a word consisting of uppercase Latin letters. The prettiness of the song is the prettiness of its title.

Let's define the simple prettiness of a word as the ratio of the number of vowels in the word to the number of all letters in the word.

Let's define the prettiness of a word as the sum of simple prettiness of all the substrings of the word.

More formally, let's define the function vowel(c) which is equal to 1, if c is a vowel, and to 0 otherwise. Let s_{i} be the i-th character of string s, and s_{i}..j be the substring of word s, staring at the i-th character and ending at the j-th character (s_{is}_{i} + 1... s_{j}, i ≤ j).

Then the simple prettiness of s is defined by the formula:$\operatorname{simple}(s) = \frac{\sum_{i = 1}^{|s|} \operatorname{vowel}(s_{i})}{|s|}$

The prettiness of s equals $\sum_{1 \leq i \leq j \leq|s|} \operatorname{simple}(s_{i . . j})$

Find the prettiness of the given song title.

We assume that the vowels are I, E, A, O, U, Y.


-----Input-----

The input contains a single string s (1 ≤ |s| ≤ 5·10^5) — the title of the song.


-----Output-----

Print the prettiness of the song with the absolute or relative error of at most 10^{ - 6}.


-----Examples-----
Input
IEAIAIO

Output
28.0000000

Input
BYOB

Output
5.8333333

Input
YISVOWEL

Output
17.0500000



-----Note-----

In the first sample all letters are vowels. The simple prettiness of each substring is 1. The word of length 7 has 28 substrings. So, the prettiness of the song equals to 28.
user: Dr. Bruce Banner hates his enemies (like others don't). As we all know, he can barely talk when he turns into the incredible Hulk. That's why he asked you to help him to express his feelings.

Hulk likes the Inception so much, and like that his feelings are complicated. They have n layers. The first layer is hate, second one is love, third one is hate and so on...

For example if n = 1, then his feeling is "I hate it" or if n = 2 it's "I hate that I love it", and if n = 3 it's "I hate that I love that I hate it" and so on.

Please help Dr. Banner.


-----Input-----

The only line of the input contains a single integer n (1 ≤ n ≤ 100) — the number of layers of love and hate.


-----Output-----

Print Dr.Banner's feeling in one line.


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

Output
I hate it

Input
2

Output
I hate that I love it

Input
3

Output
I hate that I love that I hate it
user: You are a given a list of integers $a_1, a_2, \ldots, a_n$ and $s$ of its segments $[l_j; r_j]$ (where $1 \le l_j \le r_j \le n$).

You need to select exactly $m$ segments in such a way that the $k$-th order statistic of the multiset of $a_i$, where $i$ is contained in at least one segment, is the smallest possible. If it's impossible to select a set of $m$ segments in such a way that the multiset contains at least $k$ elements, print -1.

The $k$-th order statistic of a multiset is the value of the $k$-th element after sorting the multiset in non-descending order.


-----Input-----

The first line contains four integers $n$, $s$, $m$ and $k$ ($1 \le m \le s \le 1500$, $1 \le k \le n \le 1500$) — the size of the list, the number of segments, the number of segments to choose and the statistic number.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the values of the numbers in the list.

Each of the next $s$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the endpoints of the segments.

It is possible that some segments coincide.


-----Output-----

Print exactly one integer — the smallest possible $k$-th order statistic, or -1 if it's impossible to choose segments in a way that the multiset contains at least $k$ elements.


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

Output
2

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

Output
1

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

Output
-1



-----Note-----

In the first example, one possible solution is to choose the first and the third segment. Together they will cover three elements of the list (all, except for the third one). This way the $2$-nd order statistic for the covered elements is $2$.

[Image]
user: This time the Berland Team Olympiad in Informatics is held in a remote city that can only be reached by one small bus. Bus has n passenger seats, seat i can be occupied only by a participant from the city a_{i}.

Today the bus has completed m trips, each time bringing n participants. The participants were then aligned in one line in the order they arrived, with people from the same bus standing in the order of their seats (i. e. if we write down the cities where the participants came from, we get the sequence a_1, a_2, ..., a_{n} repeated m times).

After that some teams were formed, each consisting of k participants form the same city standing next to each other in the line. Once formed, teams left the line. The teams were formed until there were no k neighboring participants from the same city.

Help the organizers determine how many participants have left in the line after that process ended. We can prove that answer doesn't depend on the order in which teams were selected.


-----Input-----

The first line contains three integers n, k and m (1 ≤ n ≤ 10^5, 2 ≤ k ≤ 10^9, 1 ≤ m ≤ 10^9).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5), where a_{i} is the number of city, person from which must take seat i in the bus. 


-----Output-----

Output the number of remaining participants in the line.


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

Output
12

Input
1 9 10
1

Output
1

Input
3 2 10
1 2 1

Output
0



-----Note-----

In the second example, the line consists of ten participants from the same city. Nine of them will form a team. At the end, only one participant will stay in the line.
user: Vova promised himself that he would never play computer games... But recently Firestorm — a well-known game developing company — published their newest game, World of Farcraft, and it became really popular. Of course, Vova started playing it.

Now he tries to solve a quest. The task is to come to a settlement named Overcity and spread a rumor in it.

Vova knows that there are n characters in Overcity. Some characters are friends to each other, and they share information they got. Also Vova knows that he can bribe each character so he or she starts spreading the rumor; i-th character wants c_{i} gold in exchange for spreading the rumor. When a character hears the rumor, he tells it to all his friends, and they start spreading the rumor to their friends (for free), and so on.

The quest is finished when all n characters know the rumor. What is the minimum amount of gold Vova needs to spend in order to finish the quest?

Take a look at the notes if you think you haven't understood the problem completely.


-----Input-----

The first line contains two integer numbers n and m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5) — the number of characters in Overcity and the number of pairs of friends.

The second line contains n integer numbers c_{i} (0 ≤ c_{i} ≤ 10^9) — the amount of gold i-th character asks to start spreading the rumor.

Then m lines follow, each containing a pair of numbers (x_{i}, y_{i}) which represent that characters x_{i} and y_{i} are friends (1 ≤ x_{i}, y_{i} ≤ n, x_{i} ≠ y_{i}). It is guaranteed that each pair is listed at most once.


-----Output-----

Print one number — the minimum amount of gold Vova has to spend in order to finish the quest.


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

Output
10

Input
10 0
1 2 3 4 5 6 7 8 9 10

Output
55

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

Output
15



-----Note-----

In the first example the best decision is to bribe the first character (he will spread the rumor to fourth character, and the fourth one will spread it to fifth). Also Vova has to bribe the second and the third characters, so they know the rumor.

In the second example Vova has to bribe everyone.

In the third example the optimal decision is to bribe the first, the third, the fifth, the seventh and the ninth characters.
user: Arcady is a copywriter. His today's task is to type up an already well-designed story using his favorite text editor.

Arcady types words, punctuation signs and spaces one after another. Each letter and each sign (including line feed) requires one keyboard click in order to be printed. Moreover, when Arcady has a non-empty prefix of some word on the screen, the editor proposes a possible autocompletion for this word, more precisely one of the already printed words such that its prefix matches the currently printed prefix if this word is unique. For example, if Arcady has already printed «codeforces», «coding» and «codeforces» once again, then there will be no autocompletion attempt for «cod», but if he proceeds with «code», the editor will propose «codeforces».

With a single click Arcady can follow the editor's proposal, i.e. to transform the current prefix to it. Note that no additional symbols are printed after the autocompletion (no spaces, line feeds, etc). What is the minimum number of keyboard clicks Arcady has to perform to print the entire text, if he is not allowed to move the cursor or erase the already printed symbols?

A word here is a contiguous sequence of latin letters bordered by spaces, punctuation signs and line/text beginnings/ends. Arcady uses only lowercase letters. For example, there are 20 words in «it's well-known that tic-tac-toe is a paper-and-pencil game for two players, x and o.».


-----Input-----

The only line contains Arcady's text, consisting only of lowercase latin letters, spaces, line feeds and the following punctuation signs: «.», «,», «?», «!», «'» and «-». The total amount of symbols doesn't exceed 3·10^5. It's guaranteed that all lines are non-empty.


-----Output-----

Print a single integer — the minimum number of clicks.


-----Examples-----
Input
snow affects sports such as skiing, snowboarding, and snowmachine travel.
snowboarding is a recreational activity and olympic and paralympic sport.

Output
141

Input
'co-co-co, codeforces?!'

Output
25

Input
thun-thun-thunder, thunder, thunder
thunder, thun-, thunder
thun-thun-thunder, thunder
thunder, feel the thunder
lightning then the thunder
thunder, feel the thunder
lightning then the thunder
thunder, thunder

Output
183



-----Note-----

In sample case one it's optimal to use autocompletion for the first instance of «snowboarding» after typing up «sn» and for the second instance of «snowboarding» after typing up «snowb». This will save 7 clicks.

In sample case two it doesn't matter whether to use autocompletion or not.
user: Stepan is a very experienced olympiad participant. He has n cups for Physics olympiads and m cups for Informatics olympiads. Each cup is characterized by two parameters — its significance c_{i} and width w_{i}.

Stepan decided to expose some of his cups on a shelf with width d in such a way, that:  there is at least one Physics cup and at least one Informatics cup on the shelf,  the total width of the exposed cups does not exceed d,  from each subjects (Physics and Informatics) some of the most significant cups are exposed (i. e. if a cup for some subject with significance x is exposed, then all the cups for this subject with significance greater than x must be exposed too). 

Your task is to determine the maximum possible total significance, which Stepan can get when he exposes cups on the shelf with width d, considering all the rules described above. The total significance is the sum of significances of all the exposed cups.


-----Input-----

The first line contains three integers n, m and d (1 ≤ n, m ≤ 100 000, 1 ≤ d ≤ 10^9) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf.

Each of the following n lines contains two integers c_{i} and w_{i} (1 ≤ c_{i}, w_{i} ≤ 10^9) — significance and width of the i-th cup for Physics olympiads.

Each of the following m lines contains two integers c_{j} and w_{j} (1 ≤ c_{j}, w_{j} ≤ 10^9) — significance and width of the j-th cup for Informatics olympiads.


-----Output-----

Print the maximum possible total significance, which Stepan can get exposing cups on the shelf with width d, considering all the rules described in the statement.

If there is no way to expose cups on the shelf, then print 0.


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

Output
8

Input
4 3 12
3 4
2 4
3 5
3 4
3 5
5 2
3 4

Output
11

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

Output
0



-----Note-----

In the first example Stepan has only one Informatics cup which must be exposed on the shelf. Its significance equals 3 and width equals 2, so after Stepan exposes it, the width of free space on the shelf becomes equal to 6. Also, Stepan must expose the second Physics cup (which has width 5), because it is the most significant cup for Physics (its significance equals 5). After that Stepan can not expose more cups on the shelf, because there is no enough free space. Thus, the maximum total significance of exposed cups equals to 8.
user: Vasya is preparing a contest, and now he has written a statement for an easy problem. The statement is a string of length $n$ consisting of lowercase Latin latters. Vasya thinks that the statement can be considered hard if it contains a subsequence hard; otherwise the statement is easy. For example, hard, hzazrzd, haaaaard can be considered hard statements, while har, hart and drah are easy statements. 

Vasya doesn't want the statement to be hard. He may remove some characters from the statement in order to make it easy. But, of course, some parts of the statement can be crucial to understanding. Initially the ambiguity of the statement is $0$, and removing $i$-th character increases the ambiguity by $a_i$ (the index of each character is considered as it was in the original statement, so, for example, if you delete character r from hard, and then character d, the index of d is still $4$ even though you delete it from the string had).

Vasya wants to calculate the minimum ambiguity of the statement, if he removes some characters (possibly zero) so that the statement is easy. Help him to do it!

Recall that subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 10^5$) — the length of the statement.

The second line contains one string $s$ of length $n$, consisting of lowercase Latin letters — the statement written by Vasya.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 998244353$).


-----Output-----

Print minimum possible ambiguity of the statement after Vasya deletes some (possibly zero) characters so the resulting statement is easy.


-----Examples-----
Input
6
hhardh
3 2 9 11 7 1

Output
5

Input
8
hhzarwde
3 2 6 9 4 8 7 1

Output
4

Input
6
hhaarr
1 2 3 4 5 6

Output
0



-----Note-----

In the first example, first two characters are removed so the result is ardh.

In the second example, $5$-th character is removed so the result is hhzawde.

In the third example there's no need to remove anything.
user: Little Artem likes electronics. He can spend lots of time making different schemas and looking for novelties in the nearest electronics store. The new control element was delivered to the store recently and Artem immediately bought it.

That element can store information about the matrix of integers size n × m. There are n + m inputs in that element, i.e. each row and each column can get the signal. When signal comes to the input corresponding to some row, this row cyclically shifts to the left, that is the first element of the row becomes last element, second element becomes first and so on. When signal comes to the input corresponding to some column, that column shifts cyclically to the top, that is first element of the column becomes last element, second element becomes first and so on. Rows are numbered with integers from 1 to n from top to bottom, while columns are numbered with integers from 1 to m from left to right.

Artem wants to carefully study this element before using it. For that purpose he is going to set up an experiment consisting of q turns. On each turn he either sends the signal to some input or checks what number is stored at some position of the matrix.

Artem has completed his experiment and has written down the results, but he has lost the chip! Help Artem find any initial matrix that will match the experiment results. It is guaranteed that experiment data is consistent, which means at least one valid matrix exists.


-----Input-----

The first line of the input contains three integers n, m and q (1 ≤ n, m ≤ 100, 1 ≤ q ≤ 10 000) — dimensions of the matrix and the number of turns in the experiment, respectively.

Next q lines contain turns descriptions, one per line. Each description starts with an integer t_{i} (1 ≤ t_{i} ≤ 3) that defines the type of the operation. For the operation of first and second type integer r_{i} (1 ≤ r_{i} ≤ n) or c_{i} (1 ≤ c_{i} ≤ m) follows, while for the operations of the third type three integers r_{i}, c_{i} and x_{i} (1 ≤ r_{i} ≤ n, 1 ≤ c_{i} ≤ m,  - 10^9 ≤ x_{i} ≤ 10^9) are given.

Operation of the first type (t_{i} = 1) means that signal comes to the input corresponding to row r_{i}, that is it will shift cyclically. Operation of the second type (t_{i} = 2) means that column c_{i} will shift cyclically. Finally, operation of the third type means that at this moment of time cell located in the row r_{i} and column c_{i} stores value x_{i}.


-----Output-----

Print the description of any valid initial matrix as n lines containing m integers each. All output integers should not exceed 10^9 by their absolute value.

If there are multiple valid solutions, output any of them.


-----Examples-----
Input
2 2 6
2 1
2 2
3 1 1 1
3 2 2 2
3 1 2 8
3 2 1 8

Output
8 2 
1 8 

Input
3 3 2
1 2
3 2 2 5

Output
0 0 0 
0 0 5 
0 0 0
user: IT City company developing computer games decided to upgrade its way to reward its employees. Now it looks the following way. After a new game release users start buying it actively, and the company tracks the number of sales with precision to each transaction. Every time when the next number of sales is not divisible by any number from 2 to 10 every developer of this game gets a small bonus.

A game designer Petya knows that the company is just about to release a new game that was partly developed by him. On the basis of his experience he predicts that n people will buy the game during the first month. Now Petya wants to determine how many times he will get the bonus. Help him to know it.


-----Input-----

The only line of the input contains one integer n (1 ≤ n ≤ 10^18) — the prediction on the number of people who will buy the game.


-----Output-----

Output one integer showing how many numbers from 1 to n are not divisible by any number from 2 to 10.


-----Examples-----
Input
12

Output
2