meetforever/GRPO_CL huggingface dataset:
user: Consider some set of distinct characters $A$ and some string $S$, consisting of exactly $n$ characters, where each character is present in $A$.

You are given an array of $m$ integers $b$ ($b_1 < b_2 < \dots < b_m$). 

You are allowed to perform the following move on the string $S$:

  Choose some valid $i$ and set $k = b_i$;  Take the first $k$ characters of $S = Pr_k$;  Take the last $k$ characters of $S = Su_k$;  Substitute the first $k$ characters of $S$ with the reversed $Su_k$;  Substitute the last $k$ characters of $S$ with the reversed $Pr_k$. 

For example, let's take a look at $S =$ "abcdefghi" and $k = 2$. $Pr_2 =$ "ab", $Su_2 =$ "hi". Reversed $Pr_2 =$ "ba", $Su_2 =$ "ih". Thus, the resulting $S$ is "ihcdefgba".

The move can be performed arbitrary number of times (possibly zero). Any $i$ can be selected multiple times over these moves.

Let's call some strings $S$ and $T$ equal if and only if there exists such a sequence of moves to transmute string $S$ to string $T$. For the above example strings "abcdefghi" and "ihcdefgba" are equal. Also note that this implies $S = S$.

The task is simple. Count the number of distinct strings.

The answer can be huge enough, so calculate it modulo $998244353$.


-----Input-----

The first line contains three integers $n$, $m$ and $|A|$ ($2 \le n \le 10^9$, $1 \le m \le min(\frac n 2, 2 \cdot 10^5)$, $1 \le |A| \le 10^9$) — the length of the strings, the size of the array $b$ and the size of the set $A$, respectively.

The second line contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le \frac n 2$, $b_1 < b_2 < \dots < b_m$).


-----Output-----

Print a single integer — the number of distinct strings of length $n$ with characters from set $A$ modulo $998244353$.


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

Output
6

Input
9 2 26
2 3

Output
150352234

Input
12 3 1
2 5 6

Output
1



-----Note-----

Here are all the distinct strings for the first example. The chosen letters 'a' and 'b' are there just to show that the characters in $A$ are different. 

  "aaa"  "aab" = "baa"  "aba"  "abb" = "bba"  "bab"  "bbb"
user: You have a multiset containing several integers. Initially, it contains $a_1$ elements equal to $1$, $a_2$ elements equal to $2$, ..., $a_n$ elements equal to $n$.

You may apply two types of operations:  choose two integers $l$ and $r$ ($l \le r$), then remove one occurrence of $l$, one occurrence of $l + 1$, ..., one occurrence of $r$ from the multiset. This operation can be applied only if each number from $l$ to $r$ occurs at least once in the multiset;  choose two integers $i$ and $x$ ($x \ge 1$), then remove $x$ occurrences of $i$ from the multiset. This operation can be applied only if the multiset contains at least $x$ occurrences of $i$. 

What is the minimum number of operations required to delete all elements from the multiset?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 5000$).

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


-----Output-----

Print one integer — the minimum number of operations required to delete all elements from the multiset.


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

Output
2

Input
5
1 0 1 0 1

Output
3
user: ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear! 

More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.

For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.

You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.


-----Input-----

The first line contains two integers n and c (1 ≤ n ≤ 100 000, 1 ≤ c ≤ 10^9) — the number of words ZS the Coder typed and the crazy computer delay respectively.

The next line contains n integers t_1, t_2, ..., t_{n} (1 ≤ t_1 < t_2 < ... < t_{n} ≤ 10^9), where t_{i} denotes the second when ZS the Coder typed the i-th word.


-----Output-----

Print a single positive integer, the number of words that remain on the screen after all n words was typed, in other words, at the second t_{n}.


-----Examples-----
Input
6 5
1 3 8 14 19 20

Output
3
Input
6 1
1 3 5 7 9 10

Output
2


-----Note-----

The first sample is already explained in the problem statement.

For the second sample, after typing the first word at the second 1, it disappears because the next word is typed at the second 3 and 3 - 1 > 1. Similarly, only 1 word will remain at the second 9. Then, a word is typed at the second 10, so there will be two words on the screen, as the old word won't disappear because 10 - 9 ≤ 1.
user: Devu is a dumb guy, his learning curve is very slow. You are supposed to teach him n subjects, the i^{th} subject has c_{i} chapters. When you teach him, you are supposed to teach all the chapters of a subject continuously.

Let us say that his initial per chapter learning power of a subject is x hours. In other words he can learn a chapter of a particular subject in x hours.

Well Devu is not complete dumb, there is a good thing about him too. If you teach him a subject, then time required to teach any chapter of the next subject will require exactly 1 hour less than previously required (see the examples to understand it more clearly). Note that his per chapter learning power can not be less than 1 hour.

You can teach him the n subjects in any possible order. Find out minimum amount of time (in hours) Devu will take to understand all the subjects and you will be free to do some enjoying task rather than teaching a dumb guy.

Please be careful that answer might not fit in 32 bit data type.


-----Input-----

The first line will contain two space separated integers n, x (1 ≤ n, x ≤ 10^5). The next line will contain n space separated integers: c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^5).


-----Output-----

Output a single integer representing the answer to the problem.


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

Output
11

Input
4 2
5 1 2 1

Output
10

Input
3 3
1 1 1

Output
6



-----Note-----

Look at the first example. Consider the order of subjects: 1, 2. When you teach Devu the first subject, it will take him 3 hours per chapter, so it will take 12 hours to teach first subject. After teaching first subject, his per chapter learning time will be 2 hours. Now teaching him second subject will take 2 × 1 = 2 hours. Hence you will need to spend 12 + 2 = 14 hours.

Consider the order of subjects: 2, 1. When you teach Devu the second subject, then it will take him 3 hours per chapter, so it will take 3 × 1 = 3 hours to teach the second subject. After teaching the second subject, his per chapter learning time will be 2 hours. Now teaching him the first subject will take 2 × 4 = 8 hours. Hence you will need to spend 11 hours.

So overall, minimum of both the cases is 11 hours.

Look at the third example. The order in this example doesn't matter. When you teach Devu the first subject, it will take him 3 hours per chapter. When you teach Devu the second subject, it will take him 2 hours per chapter. When you teach Devu the third subject, it will take him 1 hours per chapter. In total it takes 6 hours.
user: It was decided in IT City to distinguish successes of local IT companies by awards in the form of stars covered with gold from one side. To order the stars it is necessary to estimate order cost that depends on the area of gold-plating. Write a program that can calculate the area of a star.

A "star" figure having n ≥ 5 corners where n is a prime number is constructed the following way. On the circle of radius r n points are selected so that the distances between the adjacent ones are equal. Then every point is connected by a segment with two maximally distant points. All areas bounded by the segments parts are the figure parts. [Image] 


-----Input-----

The only line of the input contains two integers n (5 ≤ n < 10^9, n is prime) and r (1 ≤ r ≤ 10^9) — the number of the star corners and the radius of the circumcircle correspondingly.


-----Output-----

Output one number — the star area. The relative error of your answer should not be greater than 10^{ - 7}.


-----Examples-----
Input
7 10

Output
108.395919545675
user: Emily's birthday is next week and Jack has decided to buy a present for her. He knows she loves books so he goes to the local bookshop, where there are n books on sale from one of m genres.

In the bookshop, Jack decides to buy two books of different genres.

Based on the genre of books on sale in the shop, find the number of options available to Jack for choosing two books of different genres for Emily. Options are considered different if they differ in at least one book.

The books are given by indices of their genres. The genres are numbered from 1 to m.


-----Input-----

The first line contains two positive integers n and m (2 ≤ n ≤ 2·10^5, 2 ≤ m ≤ 10) — the number of books in the bookstore and the number of genres.

The second line contains a sequence a_1, a_2, ..., a_{n}, where a_{i} (1 ≤ a_{i} ≤ m) equals the genre of the i-th book.

It is guaranteed that for each genre there is at least one book of that genre.


-----Output-----

Print the only integer — the number of ways in which Jack can choose books.

It is guaranteed that the answer doesn't exceed the value 2·10^9.


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

Output
5

Input
7 4
4 2 3 1 2 4 3

Output
18



-----Note-----

The answer to the first test sample equals 5 as Sasha can choose:  the first and second books,  the first and third books,  the first and fourth books,  the second and third books,  the third and fourth books.
user: IT City administration has no rest because of the fame of the Pyramids in Egypt. There is a project of construction of pyramid complex near the city in the place called Emerald Walley. The distinction of the complex is that its pyramids will be not only quadrangular as in Egypt but also triangular and pentagonal. Of course the amount of the city budget funds for the construction depends on the pyramids' volume. Your task is to calculate the volume of the pilot project consisting of three pyramids — one triangular, one quadrangular and one pentagonal.

The first pyramid has equilateral triangle as its base, and all 6 edges of the pyramid have equal length. The second pyramid has a square as its base and all 8 edges of the pyramid have equal length. The third pyramid has a regular pentagon as its base and all 10 edges of the pyramid have equal length. [Image] 


-----Input-----

The only line of the input contains three integers l_3, l_4, l_5 (1 ≤ l_3, l_4, l_5 ≤ 1000) — the edge lengths of triangular, quadrangular and pentagonal pyramids correspondingly.


-----Output-----

Output one number — the total volume of the pyramids. Absolute or relative error should not be greater than 10^{ - 9}.


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

Output
38.546168065709
user: Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral. 


-----Input-----

The first line contains integer n (4 ≤ n ≤ 300). Each of the next n lines contains two integers: x_{i}, y_{i} ( - 1000 ≤ x_{i}, y_{i} ≤ 1000) — the cartesian coordinates of ith special point. It is guaranteed that no three points are on the same line. It is guaranteed that no two points coincide. 


-----Output-----

Output a single real number — the maximal area of a special quadrilateral. The answer will be considered correct if its absolute or relative error does't exceed 10^{ - 9}.


-----Examples-----
Input
5
0 0
0 4
4 0
4 4
2 3

Output
16.000000


-----Note-----

In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is 4·4 = 16.
user: You are given a tree (a connected undirected graph without cycles) of $n$ vertices. Each of the $n - 1$ edges of the tree is colored in either black or red.

You are also given an integer $k$. Consider sequences of $k$ vertices. Let's call a sequence $[a_1, a_2, \ldots, a_k]$ good if it satisfies the following criterion:  We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from $a_1$ and ending at $a_k$.  Start at $a_1$, then go to $a_2$ using the shortest path between $a_1$ and $a_2$, then go to $a_3$ in a similar way, and so on, until you travel the shortest path between $a_{k-1}$ and $a_k$. If you walked over at least one black edge during this process, then the sequence is good.  [Image] 

Consider the tree on the picture. If $k=3$ then the following sequences are good: $[1, 4, 7]$, $[5, 5, 3]$ and $[2, 3, 7]$. The following sequences are not good: $[1, 4, 6]$, $[5, 5, 5]$, $[3, 7, 3]$.

There are $n^k$ sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo $10^9+7$.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $2 \le k \le 100$), the size of the tree and the length of the vertex sequence.

Each of the next $n - 1$ lines contains three integers $u_i$, $v_i$ and $x_i$ ($1 \le u_i, v_i \le n$, $x_i \in \{0, 1\}$), where $u_i$ and $v_i$ denote the endpoints of the corresponding edge and $x_i$ is the color of this edge ($0$ denotes red edge and $1$ denotes black edge).


-----Output-----

Print the number of good sequences modulo $10^9 + 7$.


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

Output
252
Input
4 6
1 2 0
1 3 0
1 4 0

Output
0
Input
3 5
1 2 1
2 3 0

Output
210


-----Note-----

In the first example, all sequences ($4^4$) of length $4$ except the following are good:   $[1, 1, 1, 1]$ $[2, 2, 2, 2]$ $[3, 3, 3, 3]$ $[4, 4, 4, 4]$ 

In the second example, all edges are red, hence there aren't any good sequences.
user: Two neighboring kingdoms decided to build a wall between them with some gates to enable the citizens to go from one kingdom to another. Each time a citizen passes through a gate, he has to pay one silver coin.

The world can be represented by the first quadrant of a plane and the wall is built along the identity line (i.e. the line with the equation x = y). Any point below the wall belongs to the first kingdom while any point above the wall belongs to the second kingdom. There is a gate at any integer point on the line (i.e. at points (0, 0), (1, 1), (2, 2), ...). The wall and the gates do not belong to any of the kingdoms. 

Fafa is at the gate at position (0, 0) and he wants to walk around in the two kingdoms. He knows the sequence S of moves he will do. This sequence is a string where each character represents a move. The two possible moves Fafa will do are 'U' (move one step up, from (x, y) to (x, y + 1)) and 'R' (move one step right, from (x, y) to (x + 1, y)). 

Fafa wants to know the number of silver coins he needs to pay to walk around the two kingdoms following the sequence S. Note that if Fafa visits a gate without moving from one kingdom to another, he pays no silver coins. Also assume that he doesn't pay at the gate at point (0, 0), i. e. he is initially on the side he needs. 


-----Input-----

The first line of the input contains single integer n (1 ≤ n ≤ 10^5) — the number of moves in the walking sequence.

The second line contains a string S of length n consisting of the characters 'U' and 'R' describing the required moves. Fafa will follow the sequence S in order from left to right.


-----Output-----

On a single line, print one integer representing the number of silver coins Fafa needs to pay at the gates to follow the sequence S.


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

Output
0

Input
6
RURUUR

Output
1

Input
7
URRRUUU

Output
2



-----Note-----

The figure below describes the third sample. The red arrows represent the sequence of moves Fafa will follow. The green gates represent the gates at which Fafa have to pay silver coins. [Image]
user: Vanya has a table consisting of 100 rows, each row contains 100 cells. The rows are numbered by integers from 1 to 100 from bottom to top, the columns are numbered from 1 to 100 from left to right. 

In this table, Vanya chose n rectangles with sides that go along borders of squares (some rectangles probably occur multiple times). After that for each cell of the table he counted the number of rectangles it belongs to and wrote this number into it. Now he wants to find the sum of values in all cells of the table and as the table is too large, he asks you to help him find the result.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of rectangles.

Each of the following n lines contains four integers x_1, y_1, x_2, y_2 (1 ≤ x_1 ≤ x_2 ≤ 100, 1 ≤ y_1 ≤ y_2 ≤ 100), where x_1 and y_1 are the number of the column and row of the lower left cell and x_2 and y_2 are the number of the column and row of the upper right cell of a rectangle.


-----Output-----

In a single line print the sum of all values in the cells of the table.


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

Output
10

Input
2
1 1 3 3
1 1 3 3

Output
18



-----Note-----

Note to the first sample test:

Values of the table in the first three rows and columns will be as follows:

121

121

110

So, the sum of values will be equal to 10.

Note to the second sample test:

Values of the table in the first three rows and columns will be as follows:

222

222

222

So, the sum of values will be equal to 18.
user: The polar bears are going fishing. They plan to sail from (s_{x}, s_{y}) to (e_{x}, e_{y}). However, the boat can only sail by wind. At each second, the wind blows in one of these directions: east, south, west or north. Assume the boat is currently at (x, y).  If the wind blows to the east, the boat will move to (x + 1, y).  If the wind blows to the south, the boat will move to (x, y - 1).  If the wind blows to the west, the boat will move to (x - 1, y).  If the wind blows to the north, the boat will move to (x, y + 1). 

Alternatively, they can hold the boat by the anchor. In this case, the boat stays at (x, y). Given the wind direction for t seconds, what is the earliest time they sail to (e_{x}, e_{y})?


-----Input-----

The first line contains five integers t, s_{x}, s_{y}, e_{x}, e_{y} (1 ≤ t ≤ 10^5,  - 10^9 ≤ s_{x}, s_{y}, e_{x}, e_{y} ≤ 10^9). The starting location and the ending location will be different.

The second line contains t characters, the i-th character is the wind blowing direction at the i-th second. It will be one of the four possibilities: "E" (east), "S" (south), "W" (west) and "N" (north).


-----Output-----

If they can reach (e_{x}, e_{y}) within t seconds, print the earliest time they can achieve it. Otherwise, print "-1" (without quotes).


-----Examples-----
Input
5 0 0 1 1
SESNW

Output
4

Input
10 5 3 3 6
NENSWESNEE

Output
-1



-----Note-----

In the first sample, they can stay at seconds 1, 3, and move at seconds 2, 4.

In the second sample, they cannot sail to the destination.
user: The protection of a popular program developed by one of IT City companies is organized the following way. After installation it outputs a random five digit number which should be sent in SMS to a particular phone number. In response an SMS activation code arrives.

A young hacker Vasya disassembled the program and found the algorithm that transforms the shown number into the activation code. Note: it is clear that Vasya is a law-abiding hacker, and made it for a noble purpose — to show the developer the imperfection of their protection.

The found algorithm looks the following way. At first the digits of the number are shuffled in the following order <first digit><third digit><fifth digit><fourth digit><second digit>. For example the shuffle of 12345 should lead to 13542. On the second stage the number is raised to the fifth power. The result of the shuffle and exponentiation of the number 12345 is 455 422 043 125 550 171 232. The answer is the 5 last digits of this result. For the number 12345 the answer should be 71232.

Vasya is going to write a keygen program implementing this algorithm. Can you do the same?


-----Input-----

The only line of the input contains a positive integer five digit number for which the activation code should be found.


-----Output-----

Output exactly 5 digits without spaces between them — the found activation code of the program.


-----Examples-----
Input
12345

Output
71232
user: Professor Ibrahim has prepared the final homework for his algorithm’s class. He asked his students to implement the Posterization Image Filter.

Their algorithm will be tested on an array of integers, where the $i$-th integer represents the color of the $i$-th pixel in the image. The image is in black and white, therefore the color of each pixel will be an integer between 0 and 255 (inclusive).

To implement the filter, students are required to divide the black and white color range [0, 255] into groups of consecutive colors, and select one color in each group to be the group’s key. In order to preserve image details, the size of a group must not be greater than $k$, and each color should belong to exactly one group.

Finally, the students will replace the color of each pixel in the array with that color’s assigned group key.

To better understand the effect, here is an image of a basking turtle where the Posterization Filter was applied with increasing $k$ to the right. 

 [Image] 

To make the process of checking the final answer easier, Professor Ibrahim wants students to divide the groups and assign the keys in a way that produces the lexicographically smallest possible array.


-----Input-----

The first line of input contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 256$), the number of pixels in the image, and the maximum size of a group, respectively.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \leq p_i \leq 255$), where $p_i$ is the color of the $i$-th pixel.


-----Output-----

Print $n$ space-separated integers; the lexicographically smallest possible array that represents the image after applying the Posterization filter.


-----Examples-----
Input
4 3
2 14 3 4

Output
0 12 3 3

Input
5 2
0 2 1 255 254

Output
0 1 1 254 254



-----Note-----

One possible way to group colors and assign keys for the first sample:

Color $2$ belongs to the group $[0,2]$, with group key $0$.

Color $14$ belongs to the group $[12,14]$, with group key $12$.

Colors $3$ and $4$ belong to group $[3, 5]$, with group key $3$.

Other groups won't affect the result so they are not listed here.