meetforever/GRPO_CL huggingface dataset:
user: Famil Door wants to celebrate his birthday with his friends from Far Far Away. He has n friends and each of them can come to the party in a specific range of days of the year from a_{i} to b_{i}. Of course, Famil Door wants to have as many friends celebrating together with him as possible.

Far cars are as weird as Far Far Away citizens, so they can only carry two people of opposite gender, that is exactly one male and one female. However, Far is so far from here that no other transportation may be used to get to the party.

Famil Door should select some day of the year and invite some of his friends, such that they all are available at this moment and the number of male friends invited is equal to the number of female friends invited. Find the maximum number of friends that may present at the party.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — then number of Famil Door's friends.

Then follow n lines, that describe the friends. Each line starts with a capital letter 'F' for female friends and with a capital letter 'M' for male friends. Then follow two integers a_{i} and b_{i} (1 ≤ a_{i} ≤ b_{i} ≤ 366), providing that the i-th friend can come to the party from day a_{i} to day b_{i} inclusive.


-----Output-----

Print the maximum number of people that may come to Famil Door's party.


-----Examples-----
Input
4
M 151 307
F 343 352
F 117 145
M 24 128

Output
2

Input
6
M 128 130
F 128 131
F 131 140
F 131 141
M 131 200
M 140 200

Output
4



-----Note-----

In the first sample, friends 3 and 4 can come on any day in range [117, 128].

In the second sample, friends with indices 3, 4, 5 and 6 can come on day 140.
user: Yura has been walking for some time already and is planning to return home. He needs to get home as fast as possible. To do this, Yura can use the instant-movement locations around the city.

Let's represent the city as an area of $n \times n$ square blocks. Yura needs to move from the block with coordinates $(s_x,s_y)$ to the block with coordinates $(f_x,f_y)$. In one minute Yura can move to any neighboring by side block; in other words, he can move in four directions. Also, there are $m$ instant-movement locations in the city. Their coordinates are known to you and Yura. Yura can move to an instant-movement location in no time if he is located in a block with the same coordinate $x$ or with the same coordinate $y$ as the location.

Help Yura to find the smallest time needed to get home.


-----Input-----

The first line contains two integers $n$ and $m$ — the size of the city and the number of instant-movement locations ($1 \le n \le 10^9$, $0 \le m \le 10^5$).

The next line contains four integers $s_x$ $s_y$ $f_x$ $f_y$ — the coordinates of Yura's initial position and the coordinates of his home ($ 1 \le s_x, s_y, f_x, f_y \le n$).

Each of the next $m$ lines contains two integers $x_i$ $y_i$ — coordinates of the $i$-th instant-movement location ($1 \le x_i, y_i \le n$).


-----Output-----

In the only line print the minimum time required to get home.


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

Output
5

Input
84 5
67 59 41 2
39 56
7 2
15 3
74 18
22 7

Output
42



-----Note-----

In the first example Yura needs to reach $(5, 5)$ from $(1, 1)$. He can do that in $5$ minutes by first using the second instant-movement location (because its $y$ coordinate is equal to Yura's $y$ coordinate), and then walking $(4, 1) \to (4, 2) \to (4, 3) \to (5, 3) \to (5, 4) \to (5, 5)$.
user: There is a grid with infinitely many rows and columns. In this grid, there is a rectangular region with consecutive N rows and M columns, and a card is placed in each square in this region.
The front and back sides of these cards can be distinguished, and initially every card faces up.
We will perform the following operation once for each square contains a card:
 - For each of the following nine squares, flip the card in it if it exists: the target square itself and the eight squares that shares a corner or a side with the target square.
It can be proved that, whether each card faces up or down after all the operations does not depend on the order the operations are performed.
Find the number of cards that face down after all the operations.

-----Constraints-----
 - 1 \leq N,M \leq 10^9
 - All input values are integers.

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

-----Output-----
Print the number of cards that face down after all the operations.

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

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

We will flip every card in any of the four operations. Thus, after all the operations, all cards face up.
user: Snuke is having a barbeque party.
At the party, he will make N servings of Skewer Meal.
Example of a serving of Skewer Meal
He has a stock of 2N skewers, all of which will be used in Skewer Meal. The length of the i-th skewer is L_i.
Also, he has an infinite supply of ingredients.
To make a serving of Skewer Meal, he picks 2 skewers and threads ingredients onto those skewers.
Let the length of the shorter skewer be x, then the serving can hold the maximum of x ingredients.
What is the maximum total number of ingredients that his N servings of Skewer Meal can hold, if he uses the skewers optimally?

-----Constraints-----
 - 1≦N≦100
 - 1≦L_i≦100
 - For each i, L_i is an integer.

-----Input-----
The input is given from Standard Input in the following format:
N
L_1 L_2 ... L_{2N}

-----Output-----
Print the maximum total number of ingredients that Snuke's N servings of Skewer Meal can hold.

-----Sample Input-----
2
1 3 1 2

-----Sample Output-----
3

If he makes a serving using the first and third skewers, and another using the second and fourth skewers, each serving will hold 1 and 2 ingredients, for the total of 3.
user: Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x-direction, or move by 1 in the positive y-direction.
Let us define a function f(r, c) as follows:
 - f(r,c) :=  (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)
Given are integers r_1, r_2, c_1, and c_2.
Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2, and compute this value modulo (10^9+7).

-----Constraints-----
 - 1 ≤ r_1 ≤ r_2 ≤ 10^6
 - 1 ≤ c_1 ≤ c_2 ≤ 10^6
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
r_1 c_1 r_2 c_2

-----Output-----
Print the sum of f(i, j) modulo (10^9+7).

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

-----Sample Output-----
14

For example, there are two paths from the point (0, 0) to the point (1, 1): (0,0) → (0,1) → (1,1) and (0,0) → (1,0) → (1,1), so f(1,1)=2.
Similarly, f(1,2)=3, f(2,1)=3, and f(2,2)=6. Thus, the sum is 14.
user: Given are integers A, B, and N.
Find the maximum possible value of floor(Ax/B) - A × floor(x/B) for a non-negative integer x not greater than N.
Here floor(t) denotes the greatest integer not greater than the real number t.

-----Constraints-----
 - 1 ≤ A ≤ 10^{6}
 - 1 ≤ B ≤ 10^{12}
 - 1 ≤ N ≤ 10^{12}
 - All values in input are integers.

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

-----Output-----
Print the maximum possible value of floor(Ax/B) - A × floor(x/B) for a non-negative integer x not greater than N, as an integer.

-----Sample Input-----
5 7 4

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

When x=3, floor(Ax/B)-A×floor(x/B) = floor(15/7) - 5×floor(3/7) = 2. This is the maximum value possible.
user: Andrew skipped lessons on the subject 'Algorithms and Data Structures' for the entire term. When he came to the final test, the teacher decided to give him a difficult task as a punishment.

The teacher gave Andrew an array of n numbers a_1, ..., a_{n}. After that he asked Andrew for each k from 1 to n - 1 to build a k-ary heap on the array and count the number of elements for which the property of the minimum-rooted heap is violated, i.e. the value of an element is less than the value of its parent.

Andrew looked up on the Wikipedia that a k-ary heap is a rooted tree with vertices in elements of the array. If the elements of the array are indexed from 1 to n, then the children of element v are elements with indices k(v - 1) + 2, ..., kv + 1 (if some of these elements lie outside the borders of the array, the corresponding children are absent). In any k-ary heap every element except for the first one has exactly one parent; for the element 1 the parent is absent (this element is the root of the heap). Denote p(v) as the number of the parent of the element with the number v. Let's say that for a non-root element v the property of the heap is violated if a_{v} < a_{p}(v).

Help Andrew cope with the task!


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 2·10^5).

The second line contains n space-separated integers a_1, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9).


-----Output-----

in a single line print n - 1 integers, separate the consecutive numbers with a single space — the number of elements for which the property of the k-ary heap is violated, for k = 1, 2, ..., n - 1.


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

Output
3 2 1 0

Input
6
2 2 2 2 2 2

Output
0 0 0 0 0



-----Note-----

Pictures with the heaps for the first sample are given below; elements for which the property of the heap is violated are marked with red. [Image] [Image] $\therefore$ [Image] 

In the second sample all elements are equal, so the property holds for all pairs.
user: Polycarp is a frequent user of the very popular messenger. He's chatting with his friends all the time. He has $n$ friends, numbered from $1$ to $n$.

Recall that a permutation of size $n$ is an array of size $n$ such that each integer from $1$ to $n$ occurs exactly once in this array.

So his recent chat list can be represented with a permutation $p$ of size $n$. $p_1$ is the most recent friend Polycarp talked to, $p_2$ is the second most recent and so on.

Initially, Polycarp's recent chat list $p$ looks like $1, 2, \dots, n$ (in other words, it is an identity permutation).

After that he receives $m$ messages, the $j$-th message comes from the friend $a_j$. And that causes friend $a_j$ to move to the first position in a permutation, shifting everyone between the first position and the current position of $a_j$ by $1$. Note that if the friend $a_j$ is in the first position already then nothing happens.

For example, let the recent chat list be $p = [4, 1, 5, 3, 2]$:   if he gets messaged by friend $3$, then $p$ becomes $[3, 4, 1, 5, 2]$;  if he gets messaged by friend $4$, then $p$ doesn't change $[4, 1, 5, 3, 2]$;  if he gets messaged by friend $2$, then $p$ becomes $[2, 4, 1, 5, 3]$. 

For each friend consider all position he has been at in the beginning and after receiving each message. Polycarp wants to know what were the minimum and the maximum positions.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 3 \cdot 10^5$) — the number of Polycarp's friends and the number of received messages, respectively.

The second line contains $m$ integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$) — the descriptions of the received messages.


-----Output-----

Print $n$ pairs of integers. For each friend output the minimum and the maximum positions he has been in the beginning and after receiving each message.


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

Output
1 3
2 5
1 4
1 5
1 5

Input
4 3
1 2 4

Output
1 3
1 2
3 4
1 4



-----Note-----

In the first example, Polycarp's recent chat list looks like this:   $[1, 2, 3, 4, 5]$  $[3, 1, 2, 4, 5]$  $[5, 3, 1, 2, 4]$  $[1, 5, 3, 2, 4]$  $[4, 1, 5, 3, 2]$ 

So, for example, the positions of the friend $2$ are $2, 3, 4, 4, 5$, respectively. Out of these $2$ is the minimum one and $5$ is the maximum one. Thus, the answer for the friend $2$ is a pair $(2, 5)$.

In the second example, Polycarp's recent chat list looks like this:   $[1, 2, 3, 4]$  $[1, 2, 3, 4]$  $[2, 1, 3, 4]$  $[4, 2, 1, 3]$
user: Inna loves sweets very much. That's why she decided to play a game called "Sweet Matrix".

Inna sees an n × m matrix and k candies. We'll index the matrix rows from 1 to n and the matrix columns from 1 to m. We'll represent the cell in the i-th row and j-th column as (i, j). Two cells (i, j) and (p, q) of the matrix are adjacent if |i - p| + |j - q| = 1. A path is a sequence of the matrix cells where each pair of neighbouring cells in the sequence is adjacent. We'll call the number of cells in the sequence the path's length.

Each cell of the matrix can have at most one candy. Initiallly, all the cells are empty. Inna is trying to place each of the k candies in the matrix one by one. For each candy Inna chooses cell (i, j) that will contains the candy, and also chooses the path that starts in cell (1, 1) and ends in cell (i, j) and doesn't contain any candies. After that Inna moves the candy along the path from cell (1, 1) to cell (i, j), where the candy stays forever. If at some moment Inna can't choose a path for the candy, she loses. If Inna can place all the candies in the matrix in the described manner, then her penalty equals the sum of lengths of all the paths she has used.

Help Inna to minimize the penalty in the game.


-----Input-----

The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 50, 1 ≤ k ≤ n·m).


-----Output-----

In the first line print an integer — Inna's minimum penalty in the game.

In the next k lines print the description of the path for each candy. The description of the path of the candy that is placed i-th should follow on the i-th line. The description of a path is a sequence of cells. Each cell must be written in the format (i, j), where i is the number of the row and j is the number of the column. You are allowed to print extra whitespaces in the line. If there are multiple optimal solutions, print any of them.

Please follow the output format strictly! If your program passes the first pretest, then the output format is correct.


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

Output
8
(1,1) (2,1) (2,2)
(1,1) (1,2)
(1,1) (2,1)
(1,1)



-----Note-----

Note to the sample. Initially the matrix is empty. Then Inna follows her first path, the path penalty equals the number of cells in it — 3. Note that now no path can go through cell (2, 2), as it now contains a candy. The next two candies go to cells (1, 2) and (2, 1). Inna simply leaves the last candy at cell (1, 1), the path contains only this cell. The total penalty is: 3 + 2 + 2 + 1 = 8.

Note that Inna couldn't use cell (1, 1) to place, for instance, the third candy as in this case she couldn't have made the path for the fourth candy.
user: The prison of your city has n prisoners. As the prison can't accommodate all of them, the city mayor has decided to transfer c of the prisoners to a prison located in another city.

For this reason, he made the n prisoners to stand in a line, with a number written on their chests. The number is the severity of the crime he/she has committed. The greater the number, the more severe his/her crime was.

Then, the mayor told you to choose the c prisoners, who will be transferred to the other prison. He also imposed two conditions. They are,

  The chosen c prisoners has to form a contiguous segment of prisoners.  Any of the chosen prisoner's crime level should not be greater then t. Because, that will make the prisoner a severe criminal and the mayor doesn't want to take the risk of his running away during the transfer. 

Find the number of ways you can choose the c prisoners.


-----Input-----

The first line of input will contain three space separated integers n (1 ≤ n ≤ 2·10^5), t (0 ≤ t ≤ 10^9) and c (1 ≤ c ≤ n). The next line will contain n space separated integers, the i^{th} integer is the severity i^{th} prisoner's crime. The value of crime severities will be non-negative and will not exceed 10^9. 


-----Output-----

Print a single integer — the number of ways you can choose the c prisoners.


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

Output
2

Input
1 1 1
2

Output
0

Input
11 4 2
2 2 0 7 3 2 2 4 9 1 4

Output
6
user: A permutation of size $n$ is an array of size $n$ such that each integer from $1$ to $n$ occurs exactly once in this array. An inversion in a permutation $p$ is a pair of indices $(i, j)$ such that $i > j$ and $a_i < a_j$. For example, a permutation $[4, 1, 3, 2]$ contains $4$ inversions: $(2, 1)$, $(3, 1)$, $(4, 1)$, $(4, 3)$.

You are given a permutation $p$ of size $n$. However, the numbers on some positions are replaced by $-1$. Let the valid permutation be such a replacement of $-1$ in this sequence back to numbers from $1$ to $n$ in such a way that the resulting sequence is a permutation of size $n$.

The given sequence was turned into a valid permutation randomly with the equal probability of getting each valid permutation.

Calculate the expected total number of inversions in the resulting valid permutation.

It can be shown that it is in the form of $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q \ne 0$. Report the value of $P \cdot Q^{-1} \pmod {998244353}$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the sequence.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($-1 \le p_i \le n$, $p_i \ne 0$) — the initial sequence.

It is guaranteed that all elements not equal to $-1$ are pairwise distinct.


-----Output-----

Print a single integer — the expected total number of inversions in the resulting valid permutation.

It can be shown that it is in the form of $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q \ne 0$. Report the value of $P \cdot Q^{-1} \pmod {998244353}$.


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

Output
499122179

Input
2
1 2

Output
0

Input
2
-1 -1

Output
499122177



-----Note-----

In the first example two resulting valid permutations are possible:

  $[3, 1, 2]$ — $2$ inversions;  $[3, 2, 1]$ — $3$ inversions. 

The expected value is $\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$.

In the second example no $-1$ are present, thus the only valid permutation is possible — the given one. It has $0$ inversions.

In the third example there are two resulting valid permutations — one with $0$ inversions and one with $1$ inversion.
user: A card pyramid of height $1$ is constructed by resting two cards against each other. For $h>1$, a card pyramid of height $h$ is constructed by placing a card pyramid of height $h-1$ onto a base. A base consists of $h$ pyramids of height $1$, and $h-1$ cards on top. For example, card pyramids of heights $1$, $2$, and $3$ look as follows: $\wedge A A$ 

You start with $n$ cards and build the tallest pyramid that you can. If there are some cards remaining, you build the tallest pyramid possible with the remaining cards. You repeat this process until it is impossible to build another pyramid. In the end, how many pyramids will you have constructed?


-----Input-----

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

Each test case contains a single integer $n$ ($1\le n\le 10^9$) — the number of cards.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^9$.


-----Output-----

For each test case output a single integer — the number of pyramids you will have constructed in the end.


-----Example-----
Input
5
3
14
15
24
1

Output
1
2
1
3
0



-----Note-----

In the first test, you construct a pyramid of height $1$ with $2$ cards. There is $1$ card remaining, which is not enough to build a pyramid.

In the second test, you build two pyramids, each of height $2$, with no cards remaining.

In the third test, you build one pyramid of height $3$, with no cards remaining.

In the fourth test, you build one pyramid of height $3$ with $9$ cards remaining. Then you build a pyramid of height $2$ with $2$ cards remaining. Then you build a final pyramid of height $1$ with no cards remaining.

In the fifth test, one card is not enough to build any pyramids.
user: Anton's favourite geometric figures are regular polyhedrons. Note that there are five kinds of regular polyhedrons: 

  Tetrahedron. Tetrahedron has 4 triangular faces.  Cube. Cube has 6 square faces.  Octahedron. Octahedron has 8 triangular faces.  Dodecahedron. Dodecahedron has 12 pentagonal faces.  Icosahedron. Icosahedron has 20 triangular faces. 

All five kinds of polyhedrons are shown on the picture below:

 [Image] 

Anton has a collection of n polyhedrons. One day he decided to know, how many faces his polyhedrons have in total. Help Anton and find this number!


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of polyhedrons in Anton's collection.

Each of the following n lines of the input contains a string s_{i} — the name of the i-th polyhedron in Anton's collection. The string can look like this:

  "Tetrahedron" (without quotes), if the i-th polyhedron in Anton's collection is a tetrahedron.  "Cube" (without quotes), if the i-th polyhedron in Anton's collection is a cube.  "Octahedron" (without quotes), if the i-th polyhedron in Anton's collection is an octahedron.  "Dodecahedron" (without quotes), if the i-th polyhedron in Anton's collection is a dodecahedron.  "Icosahedron" (without quotes), if the i-th polyhedron in Anton's collection is an icosahedron. 


-----Output-----

Output one number — the total number of faces in all the polyhedrons in Anton's collection.


-----Examples-----
Input
4
Icosahedron
Cube
Tetrahedron
Dodecahedron

Output
42

Input
3
Dodecahedron
Octahedron
Octahedron

Output
28



-----Note-----

In the first sample Anton has one icosahedron, one cube, one tetrahedron and one dodecahedron. Icosahedron has 20 faces, cube has 6 faces, tetrahedron has 4 faces and dodecahedron has 12 faces. In total, they have 20 + 6 + 4 + 12 = 42 faces.
user: Ivan is playing a strange game.

He has a matrix a with n rows and m columns. Each element of the matrix is equal to either 0 or 1. Rows and columns are 1-indexed. Ivan can replace any number of ones in this matrix with zeroes. After that, his score in the game will be calculated as follows:

  Initially Ivan's score is 0;  In each column, Ivan will find the topmost 1 (that is, if the current column is j, then he will find minimum i such that a_{i}, j = 1). If there are no 1's in the column, this column is skipped;  Ivan will look at the next min(k, n - i + 1) elements in this column (starting from the element he found) and count the number of 1's among these elements. This number will be added to his score. 

Of course, Ivan wants to maximize his score in this strange game. Also he doesn't want to change many elements, so he will replace the minimum possible number of ones with zeroes. Help him to determine the maximum possible score he can get and the minimum possible number of replacements required to achieve that score.


-----Input-----

The first line contains three integer numbers n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100).

Then n lines follow, i-th of them contains m integer numbers — the elements of i-th row of matrix a. Each number is either 0 or 1.


-----Output-----

Print two numbers: the maximum possible score Ivan can get and the minimum number of replacements required to get this score.


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

Output
4 1

Input
3 2 1
1 0
0 1
0 0

Output
2 0



-----Note-----

In the first example Ivan will replace the element a_{1, 2}.