meetforever/GRPO_CL huggingface dataset:
user: You are an adventurer currently journeying inside an evil temple. After defeating a couple of weak zombies, you arrived at a square room consisting of tiles forming an n × n grid. The rows are numbered 1 through n from top to bottom, and the columns are numbered 1 through n from left to right. At the far side of the room lies a door locked with evil magical forces. The following inscriptions are written on the door: The cleaning of all evil will awaken the door! 

Being a very senior adventurer, you immediately realize what this means. You notice that every single cell in the grid are initially evil. You should purify all of these cells.

The only method of tile purification known to you is by casting the "Purification" spell. You cast this spell on a single tile — then, all cells that are located in the same row and all cells that are located in the same column as the selected tile become purified (including the selected tile)! It is allowed to purify a cell more than once.

You would like to purify all n × n cells while minimizing the number of times you cast the "Purification" spell. This sounds very easy, but you just noticed that some tiles are particularly more evil than the other tiles. You cannot cast the "Purification" spell on those particularly more evil tiles, not even after they have been purified. They can still be purified if a cell sharing the same row or the same column gets selected by the "Purification" spell.

Please find some way to purify all the cells with the minimum number of spells cast. Print -1 if there is no such way.


-----Input-----

The first line will contain a single integer n (1 ≤ n ≤ 100). Then, n lines follows, each contains n characters. The j-th character in the i-th row represents the cell located at row i and column j. It will be the character 'E' if it is a particularly more evil cell, and '.' otherwise.


-----Output-----

If there exists no way to purify all the cells, output -1. Otherwise, if your solution casts x "Purification" spells (where x is the minimum possible number of spells), output x lines. Each line should consist of two integers denoting the row and column numbers of the cell on which you should cast the "Purification" spell.


-----Examples-----
Input
3
.E.
E.E
.E.

Output
1 1
2 2
3 3

Input
3
EEE
E..
E.E

Output
-1

Input
5
EE.EE
E.EE.
E...E
.EE.E
EE.EE

Output
3 3
1 3
2 2
4 4
5 3


-----Note-----

The first example is illustrated as follows. Purple tiles are evil tiles that have not yet been purified. Red tile is the tile on which "Purification" is cast. Yellow tiles are the tiles being purified as a result of the current "Purification" spell. Green tiles are tiles that have been purified previously.  [Image] 

In the second example, it is impossible to purify the cell located at row 1 and column 1.

For the third example: [Image]
user: As usual, Sereja has array a, its elements are integers: a[1], a[2], ..., a[n]. Let's introduce notation:

$f(a, l, r) = \sum_{i = l}^{r} a [ i ] ; m(a) = \operatorname{max}_{1 \leq l \leq r \leq n} f(a, l, r)$

A swap operation is the following sequence of actions:

  choose two indexes i, j (i ≠ j);  perform assignments tmp = a[i], a[i] = a[j], a[j] = tmp. 

What maximum value of function m(a) can Sereja get if he is allowed to perform at most k swap operations?


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 200; 1 ≤ k ≤ 10). The next line contains n integers a[1], a[2], ..., a[n] ( - 1000 ≤ a[i] ≤ 1000).


-----Output-----

In a single line print the maximum value of m(a) that Sereja can get if he is allowed to perform at most k swap operations.


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

Output
32

Input
5 10
-1 -1 -1 -1 -1

Output
-1
user: You are given n numbers a_1, a_2, ..., a_{n}. You can perform at most k operations. For each operation you can multiply one of the numbers by x. We want to make [Image] as large as possible, where $1$ denotes the bitwise OR. 

Find the maximum possible value of [Image] after performing at most k operations optimally.


-----Input-----

The first line contains three integers n, k and x (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10, 2 ≤ x ≤ 8).

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9).


-----Output-----

Output the maximum value of a bitwise OR of sequence elements after performing operations.


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

Output
3

Input
4 2 3
1 2 4 8

Output
79



-----Note-----

For the first sample, any possible choice of doing one operation will result the same three numbers 1, 1, 2 so the result is $1|1|2 = 3$. 

For the second sample if we multiply 8 by 3 two times we'll get 72. In this case the numbers will become 1, 2, 4, 72 so the OR value will be 79 and is the largest possible result.
user: Takahashi throws N dice, each having K sides with all integers from 1 to K. The dice are NOT pairwise distinguishable.
For each i=2,3,...,2K, find the following value modulo 998244353:
 - The number of combinations of N sides shown by the dice such that the sum of no two different sides is i.
Note that the dice are NOT distinguishable, that is, two combinations are considered different when there exists an integer k such that the number of dice showing k is different in those two.

-----Constraints-----
 - 1 \leq K \leq 2000
 - 2 \leq N \leq 2000
 - K and N are integers.

-----Input-----
Input is given from Standard Input in the following format:
K N

-----Output-----
Print 2K-1 integers. The t-th of them (1\leq t\leq 2K-1) should be the answer for i=t+1.

-----Sample Input-----
3 3

-----Sample Output-----
7
7
4
7
7

 - For i=2, the combinations (1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.
 - For i=3, the combinations (1,1,1),(1,1,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.
 - For i=4, the combinations (1,1,1),(1,1,2),(2,3,3),(3,3,3) satisfy the condition, so the answer is 4.
user: Treeland is a country in which there are n towns connected by n - 1 two-way road such that it's possible to get from any town to any other town. 

In Treeland there are 2k universities which are located in different towns. 

Recently, the president signed the decree to connect universities by high-speed network.The Ministry of Education understood the decree in its own way and decided that it was enough to connect each university with another one by using a cable. Formally, the decree will be done! 

To have the maximum sum in the budget, the Ministry decided to divide universities into pairs so that the total length of the required cable will be maximum. In other words, the total distance between universities in k pairs should be as large as possible. 

Help the Ministry to find the maximum total distance. Of course, each university should be present in only one pair. Consider that all roads have the same length which is equal to 1. 


-----Input-----

The first line of the input contains two integers n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ n / 2) — the number of towns in Treeland and the number of university pairs. Consider that towns are numbered from 1 to n. 

The second line contains 2k distinct integers u_1, u_2, ..., u_2k (1 ≤ u_{i} ≤ n) — indices of towns in which universities are located. 

The next n - 1 line contains the description of roads. Each line contains the pair of integers x_{j} and y_{j} (1 ≤ x_{j}, y_{j} ≤ n), which means that the j-th road connects towns x_{j} and y_{j}. All of them are two-way roads. You can move from any town to any other using only these roads. 


-----Output-----

Print the maximum possible sum of distances in the division of universities into k pairs.


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

Output
6

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

Output
9



-----Note-----

The figure below shows one of possible division into pairs in the first test. If you connect universities number 1 and 6 (marked in red) and universities number 2 and 5 (marked in blue) by using the cable, the total distance will equal 6 which will be the maximum sum in this example. 

 [Image]
user: Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a zebra, if it starts with a bad day, ends with a bad day, and good and bad days are alternating in it. Let us denote bad days as 0 and good days as 1. Then, for example, sequences of days 0, 010, 01010 are zebras, while sequences 1, 0110, 0101 are not.

Oleg tells you the story of days he lived in chronological order in form of string consisting of 0 and 1. Now you are interested if it is possible to divide Oleg's life history into several subsequences, each of which is a zebra, and the way it can be done. Each day must belong to exactly one of the subsequences. For each of the subsequences, days forming it must be ordered chronologically. Note that subsequence does not have to be a group of consecutive days. 


-----Input-----

In the only line of input data there is a non-empty string s consisting of characters 0 and 1, which describes the history of Oleg's life. Its length (denoted as |s|) does not exceed 200 000 characters.


-----Output-----

If there is a way to divide history into zebra subsequences, in the first line of output you should print an integer k (1 ≤ k ≤ |s|), the resulting number of subsequences. In the i-th of following k lines first print the integer l_{i} (1 ≤ l_{i} ≤ |s|), which is the length of the i-th subsequence, and then l_{i} indices of days forming the subsequence. Indices must follow in ascending order. Days are numbered starting from 1. Each index from 1 to n must belong to exactly one subsequence. If there is no way to divide day history into zebra subsequences, print -1.

Subsequences may be printed in any order. If there are several solutions, you may print any of them. You do not have to minimize nor maximize the value of k.


-----Examples-----
Input
0010100

Output
3
3 1 3 4
3 2 5 6
1 7

Input
111

Output
-1
user: It's that time of the year, Felicity is around the corner and you can see people celebrating all around the Himalayan region. The Himalayan region has n gyms. The i-th gym has g_{i} Pokemon in it. There are m distinct Pokemon types in the Himalayan region numbered from 1 to m. There is a special evolution camp set up in the fest which claims to evolve any Pokemon. The type of a Pokemon could change after evolving, subject to the constraint that if two Pokemon have the same type before evolving, they will have the same type after evolving. Also, if two Pokemon have different types before evolving, they will have different types after evolving. It is also possible that a Pokemon has the same type before and after evolving. 

Formally, an evolution plan is a permutation f of {1, 2, ..., m}, such that f(x) = y means that a Pokemon of type x evolves into a Pokemon of type y.

The gym leaders are intrigued by the special evolution camp and all of them plan to evolve their Pokemons. The protocol of the mountain states that in each gym, for every type of Pokemon, the number of Pokemon of that type before evolving any Pokemon should be equal the number of Pokemon of that type after evolving all the Pokemons according to the evolution plan. They now want to find out how many distinct evolution plans exist which satisfy the protocol.

Two evolution plans f_1 and f_2 are distinct, if they have at least one Pokemon type evolving into a different Pokemon type in the two plans, i. e. there exists an i such that f_1(i) ≠ f_2(i).

Your task is to find how many distinct evolution plans are possible such that if all Pokemon in all the gyms are evolved, the number of Pokemon of each type in each of the gyms remains the same. As the answer can be large, output it modulo 10^9 + 7.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^6) — the number of gyms and the number of Pokemon types.

The next n lines contain the description of Pokemons in the gyms. The i-th of these lines begins with the integer g_{i} (1 ≤ g_{i} ≤ 10^5) — the number of Pokemon in the i-th gym. After that g_{i} integers follow, denoting types of the Pokemons in the i-th gym. Each of these integers is between 1 and m.

The total number of Pokemons (the sum of all g_{i}) does not exceed 5·10^5.


-----Output-----

Output the number of valid evolution plans modulo 10^9 + 7.


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

Output
1

Input
1 3
3 1 2 3

Output
6

Input
2 4
2 1 2
3 2 3 4

Output
2

Input
2 2
3 2 2 1
2 1 2

Output
1

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

Output
24



-----Note-----

In the first case, the only possible evolution plan is: $1 \rightarrow 1,2 \rightarrow 2,3 \rightarrow 3$

In the second case, any permutation of (1,  2,  3) is valid.

In the third case, there are two possible plans: $1 \rightarrow 1,2 \rightarrow 2,3 \rightarrow 4,4 \rightarrow 3$ $1 \rightarrow 1,2 \rightarrow 2,3 \rightarrow 3,4 \rightarrow 4$

In the fourth case, the only possible evolution plan is: $1 \rightarrow 1,2 \rightarrow 2$
user: Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arriving, they found that citizens are worried about maximum values of the Main Uzhlyandian Function f, which is defined as follows:$f(l, r) = \sum_{i = l}^{r - 1}|a [ i ] - a [ i + 1 ]|\cdot(- 1)^{i - l}$

In the above formula, 1 ≤ l < r ≤ n must hold, where n is the size of the Main Uzhlyandian Array a, and |x| means absolute value of x. But the heroes skipped their math lessons in school, so they asked you for help. Help them calculate the maximum value of f among all possible values of l and r for the given array a.


-----Input-----

The first line contains single integer n (2 ≤ n ≤ 10^5) — the size of the array a.

The second line contains n integers a_1, a_2, ..., a_{n} (-10^9 ≤ a_{i} ≤ 10^9) — the array elements.


-----Output-----

Print the only integer — the maximum value of f.


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

Output
3
Input
4
1 5 4 7

Output
6


-----Note-----

In the first sample case, the optimal value of f is reached on intervals [1, 2] and [2, 5].

In the second case maximal value of f is reachable only on the whole array.
user: One day, little Vasya found himself in a maze consisting of (n + 1) rooms, numbered from 1 to (n + 1). Initially, Vasya is at the first room and to get out of the maze, he needs to get to the (n + 1)-th one.

The maze is organized as follows. Each room of the maze has two one-way portals. Let's consider room number i (1 ≤ i ≤ n), someone can use the first portal to move from it to room number (i + 1), also someone can use the second portal to move from it to room number p_{i}, where 1 ≤ p_{i} ≤ i.

In order not to get lost, Vasya decided to act as follows.   Each time Vasya enters some room, he paints a cross on its ceiling. Initially, Vasya paints a cross at the ceiling of room 1.  Let's assume that Vasya is in room i and has already painted a cross on its ceiling. Then, if the ceiling now contains an odd number of crosses, Vasya uses the second portal (it leads to room p_{i}), otherwise Vasya uses the first portal. 

Help Vasya determine the number of times he needs to use portals to get to room (n + 1) in the end.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^3) — the number of rooms. The second line contains n integers p_{i} (1 ≤ p_{i} ≤ i). Each p_{i} denotes the number of the room, that someone can reach, if he will use the second portal in the i-th room.


-----Output-----

Print a single number — the number of portal moves the boy needs to go out of the maze. As the number can be rather large, print it modulo 1000000007 (10^9 + 7).


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

Output
4

Input
4
1 1 2 3

Output
20

Input
5
1 1 1 1 1

Output
62
user: You invited $n$ guests to dinner! You plan to arrange one or more circles of chairs. Each chair is going to be either occupied by one guest, or be empty. You can make any number of circles. 

Your guests happen to be a little bit shy, so the $i$-th guest wants to have a least $l_i$ free chairs to the left of his chair, and at least $r_i$ free chairs to the right. The "left" and "right" directions are chosen assuming all guests are going to be seated towards the center of the circle. Note that when a guest is the only one in his circle, the $l_i$ chairs to his left and $r_i$ chairs to his right may overlap.

What is smallest total number of chairs you have to use?


-----Input-----

First line contains one integer $n$  — number of guests, ($1 \leqslant n \leqslant 10^5$). 

Next $n$ lines contain $n$ pairs of space-separated integers $l_i$ and $r_i$ ($0 \leqslant l_i, r_i \leqslant 10^9$).


-----Output-----

Output a single integer — the smallest number of chairs you have to use.


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

Output
6

Input
4
1 2
2 1
3 5
5 3

Output
15

Input
1
5 6

Output
7



-----Note-----

In the second sample the only optimal answer is to use two circles: a circle with $5$ chairs accomodating guests $1$ and $2$, and another one with $10$ chairs accomodationg guests $3$ and $4$.

In the third sample, you have only one circle with one person. The guest should have at least five free chairs to his left, and at least six free chairs to his right to the next person, which is in this case the guest herself. So, overall number of chairs should be at least 6+1=7.
user: There are n types of coins in Byteland. Conveniently, the denomination of the coin type k divides the denomination of the coin type k + 1, the denomination of the coin type 1 equals 1 tugrick. The ratio of the denominations of coin types k + 1 and k equals a_{k}. It is known that for each x there are at most 20 coin types of denomination x.

Byteasar has b_{k} coins of type k with him, and he needs to pay exactly m tugricks. It is known that Byteasar never has more than 3·10^5 coins with him. Byteasar want to know how many ways there are to pay exactly m tugricks. Two ways are different if there is an integer k such that the amount of coins of type k differs in these two ways. As all Byteland citizens, Byteasar wants to know the number of ways modulo 10^9 + 7.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 3·10^5) — the number of coin types.

The second line contains n - 1 integers a_1, a_2, ..., a_{n} - 1 (1 ≤ a_{k} ≤ 10^9) — the ratios between the coin types denominations. It is guaranteed that for each x there are at most 20 coin types of denomination x.

The third line contains n non-negative integers b_1, b_2, ..., b_{n} — the number of coins of each type Byteasar has. It is guaranteed that the sum of these integers doesn't exceed 3·10^5.

The fourth line contains single integer m (0 ≤ m < 10^10000) — the amount in tugricks Byteasar needs to pay.


-----Output-----

Print single integer — the number of ways to pay exactly m tugricks modulo 10^9 + 7.


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

4
2

Output
1

Input
2
1
4 4
2

Output
3

Input
3
3 3
10 10 10
17

Output
6



-----Note-----

In the first example Byteasar has 4 coins of denomination 1, and he has to pay 2 tugricks. There is only one way.

In the second example Byteasar has 4 coins of each of two different types of denomination 1, he has to pay 2 tugricks. There are 3 ways: pay one coin of the first type and one coin of the other, pay two coins of the first type, and pay two coins of the second type.

In the third example the denominations are equal to 1, 3, 9.
user: Programmers working on a large project have just received a task to write exactly m lines of code. There are n programmers working on a project, the i-th of them makes exactly a_{i} bugs in every line of code that he writes. 

Let's call a sequence of non-negative integers v_1, v_2, ..., v_{n} a plan, if v_1 + v_2 + ... + v_{n} = m. The programmers follow the plan like that: in the beginning the first programmer writes the first v_1 lines of the given task, then the second programmer writes v_2 more lines of the given task, and so on. In the end, the last programmer writes the remaining lines of the code. Let's call a plan good, if all the written lines of the task contain at most b bugs in total.

Your task is to determine how many distinct good plans are there. As the number of plans can be large, print the remainder of this number modulo given positive integer mod.


-----Input-----

The first line contains four integers n, m, b, mod (1 ≤ n, m ≤ 500, 0 ≤ b ≤ 500; 1 ≤ mod ≤ 10^9 + 7) — the number of programmers, the number of lines of code in the task, the maximum total number of bugs respectively and the modulo you should use when printing the answer.

The next line contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 500) — the number of bugs per line for each programmer.


-----Output-----

Print a single integer — the answer to the problem modulo mod.


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

Output
10

Input
3 6 5 1000000007
1 2 3

Output
0

Input
3 5 6 11
1 2 1

Output
0
user: You are given a text consisting of n lines. Each line contains some space-separated words, consisting of lowercase English letters.

We define a syllable as a string that contains exactly one vowel and any arbitrary number (possibly none) of consonants. In English alphabet following letters are considered to be vowels: 'a', 'e', 'i', 'o', 'u' and 'y'.

Each word of the text that contains at least one vowel can be divided into syllables. Each character should be a part of exactly one syllable. For example, the word "mamma" can be divided into syllables as "ma" and "mma", "mam" and "ma", and "mamm" and "a". Words that consist of only consonants should be ignored.

The verse patterns for the given text is a sequence of n integers p_1, p_2, ..., p_{n}. Text matches the given verse pattern if for each i from 1 to n one can divide words of the i-th line in syllables in such a way that the total number of syllables is equal to p_{i}.

You are given the text and the verse pattern. Check, if the given text matches the given verse pattern.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the number of lines in the text.

The second line contains integers p_1, ..., p_{n} (0 ≤ p_{i} ≤ 100) — the verse pattern.

Next n lines contain the text itself. Text consists of lowercase English letters and spaces. It's guaranteed that all lines are non-empty, each line starts and ends with a letter and words are separated by exactly one space. The length of each line doesn't exceed 100 characters.


-----Output-----

If the given text matches the given verse pattern, then print "YES" (without quotes) in the only line of the output. Otherwise, print "NO" (without quotes).


-----Examples-----
Input
3
2 2 3
intel
code
ch allenge

Output
YES

Input
4
1 2 3 1
a
bcdefghi
jklmnopqrstu
vwxyz

Output
NO

Input
4
13 11 15 15
to be or not to be that is the question
whether tis nobler in the mind to suffer
the slings and arrows of outrageous fortune
or to take arms against a sea of troubles

Output
YES



-----Note-----

In the first sample, one can split words into syllables in the following way: in-tel

co-de

ch al-len-ge



Since the word "ch" in the third line doesn't contain vowels, we can ignore it. As the result we get 2 syllabels in first two lines and 3 syllables in the third one.