meetforever/GRPO_CL huggingface dataset:
user: You are preparing for an exam on scheduling theory. The exam will last for exactly T milliseconds and will consist of n problems. You can either solve problem i in exactly t_{i} milliseconds or ignore it and spend no time. You don't need time to rest after solving a problem, either.

Unfortunately, your teacher considers some of the problems too easy for you. Thus, he assigned an integer a_{i} to every problem i meaning that the problem i can bring you a point to the final score only in case you have solved no more than a_{i} problems overall (including problem i).

Formally, suppose you solve problems p_1, p_2, ..., p_{k} during the exam. Then, your final score s will be equal to the number of values of j between 1 and k such that k ≤ a_{p}_{j}.

You have guessed that the real first problem of the exam is already in front of you. Therefore, you want to choose a set of problems to solve during the exam maximizing your final score in advance. Don't forget that the exam is limited in time, and you must have enough time to solve all chosen problems. If there exist different sets of problems leading to the maximum final score, any of them will do.


-----Input-----

The first line contains two integers n and T (1 ≤ n ≤ 2·10^5; 1 ≤ T ≤ 10^9) — the number of problems in the exam and the length of the exam in milliseconds, respectively.

Each of the next n lines contains two integers a_{i} and t_{i} (1 ≤ a_{i} ≤ n; 1 ≤ t_{i} ≤ 10^4). The problems are numbered from 1 to n.


-----Output-----

In the first line, output a single integer s — your maximum possible final score.

In the second line, output a single integer k (0 ≤ k ≤ n) — the number of problems you should solve.

In the third line, output k distinct integers p_1, p_2, ..., p_{k} (1 ≤ p_{i} ≤ n) — the indexes of problems you should solve, in any order.

If there are several optimal sets of problems, you may output any of them.


-----Examples-----
Input
5 300
3 100
4 150
4 80
2 90
2 300

Output
2
3
3 1 4

Input
2 100
1 787
2 788

Output
0
0


Input
2 100
2 42
2 58

Output
2
2
1 2



-----Note-----

In the first example, you should solve problems 3, 1, and 4. In this case you'll spend 80 + 100 + 90 = 270 milliseconds, falling within the length of the exam, 300 milliseconds (and even leaving yourself 30 milliseconds to have a rest). Problems 3 and 1 will bring you a point each, while problem 4 won't. You'll score two points.

In the second example, the length of the exam is catastrophically not enough to solve even a single problem.

In the third example, you have just enough time to solve both problems in 42 + 58 = 100 milliseconds and hand your solutions to the teacher with a smile.
user: Valera's finally decided to go on holiday! He packed up and headed for a ski resort.

Valera's fancied a ski trip but he soon realized that he could get lost in this new place. Somebody gave him a useful hint: the resort has n objects (we will consider the objects indexed in some way by integers from 1 to n), each object is either a hotel or a mountain.

Valera has also found out that the ski resort had multiple ski tracks. Specifically, for each object v, the resort has at most one object u, such that there is a ski track built from object u to object v. We also know that no hotel has got a ski track leading from the hotel to some object.

Valera is afraid of getting lost on the resort. So he wants you to come up with a path he would walk along. The path must consist of objects v_1, v_2, ..., v_{k} (k ≥ 1) and meet the following conditions:  Objects with numbers v_1, v_2, ..., v_{k} - 1 are mountains and the object with number v_{k} is the hotel.  For any integer i (1 ≤ i < k), there is exactly one ski track leading from object v_{i}. This track goes to object v_{i} + 1.  The path contains as many objects as possible (k is maximal). 

Help Valera. Find such path that meets all the criteria of our hero!


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of objects.

The second line contains n space-separated integers type_1, type_2, ..., type_{n} — the types of the objects. If type_{i} equals zero, then the i-th object is the mountain. If type_{i} equals one, then the i-th object is the hotel. It is guaranteed that at least one object is a hotel.

The third line of the input contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n) — the description of the ski tracks. If number a_{i} equals zero, then there is no such object v, that has a ski track built from v to i. If number a_{i} doesn't equal zero, that means that there is a track built from object a_{i} to object i.


-----Output-----

In the first line print k — the maximum possible path length for Valera. In the second line print k integers v_1, v_2, ..., v_{k} — the path. If there are multiple solutions, you can print any of them.


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

Output
5
1 2 3 4 5

Input
5
0 0 1 0 1
0 1 2 2 4

Output
2
4 5

Input
4
1 0 0 0
2 3 4 2

Output
1
1
user: One department of some software company has $n$ servers of different specifications. Servers are indexed with consecutive integers from $1$ to $n$. Suppose that the specifications of the $j$-th server may be expressed with a single integer number $c_j$ of artificial resource units.

In order for production to work, it is needed to deploy two services $S_1$ and $S_2$ to process incoming requests using the servers of the department. Processing of incoming requests of service $S_i$ takes $x_i$ resource units.

The described situation happens in an advanced company, that is why each service may be deployed using not only one server, but several servers simultaneously. If service $S_i$ is deployed using $k_i$ servers, then the load is divided equally between these servers and each server requires only $x_i / k_i$ (that may be a fractional number) resource units.

Each server may be left unused at all, or be used for deploying exactly one of the services (but not for two of them simultaneously). The service should not use more resources than the server provides.

Determine if it is possible to deploy both services using the given servers, and if yes, determine which servers should be used for deploying each of the services.


-----Input-----

The first line contains three integers $n$, $x_1$, $x_2$ ($2 \leq n \leq 300\,000$, $1 \leq x_1, x_2 \leq 10^9$) — the number of servers that the department may use, and resource units requirements for each of the services.

The second line contains $n$ space-separated integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$) — the number of resource units provided by each of the servers.


-----Output-----

If it is impossible to deploy both services using the given servers, print the only word "No" (without the quotes).

Otherwise print the word "Yes" (without the quotes). 

In the second line print two integers $k_1$ and $k_2$ ($1 \leq k_1, k_2 \leq n$) — the number of servers used for each of the services.

In the third line print $k_1$ integers, the indices of the servers that will be used for the first service.

In the fourth line print $k_2$ integers, the indices of the servers that will be used for the second service.

No index may appear twice among the indices you print in the last two lines. If there are several possible answers, it is allowed to print any of them.


-----Examples-----
Input
6 8 16
3 5 2 9 8 7

Output
Yes
3 2
1 2 6
5 4
Input
4 20 32
21 11 11 12

Output
Yes
1 3
1
2 3 4

Input
4 11 32
5 5 16 16

Output
No

Input
5 12 20
7 8 4 11 9

Output
No



-----Note-----

In the first sample test each of the servers 1, 2 and 6 will will provide $8 / 3 = 2.(6)$ resource units and each of the servers 5, 4 will provide $16 / 2 = 8$ resource units.

In the second sample test the first server will provide $20$ resource units and each of the remaining servers will provide $32 / 3 = 10.(6)$ resource units.
user: One company of IT City decided to create a group of innovative developments consisting from 5 to 7 people and hire new employees for it. After placing an advertisment the company received n resumes. Now the HR department has to evaluate each possible group composition and select one of them. Your task is to count the number of variants of group composition to evaluate.


-----Input-----

The only line of the input contains one integer n (7 ≤ n ≤ 777) — the number of potential employees that sent resumes.


-----Output-----

Output one integer — the number of different variants of group composition.


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

Output
29
user: Capitalization is writing a word with its first letter as a capital letter. Your task is to capitalize the given word.

Note, that during capitalization all the letters except the first one remains unchanged.


-----Input-----

A single line contains a non-empty word. This word consists of lowercase and uppercase English letters. The length of the word will not exceed 10^3.


-----Output-----

Output the given word after capitalization.


-----Examples-----
Input
ApPLe

Output
ApPLe

Input
konjac

Output
Konjac
user: Finally, a basketball court has been opened in SIS, so Demid has decided to hold a basketball exercise session. $2 \cdot n$ students have come to Demid's exercise session, and he lined up them into two rows of the same size (there are exactly $n$ people in each row). Students are numbered from $1$ to $n$ in each row in order from left to right.

 [Image] 

Now Demid wants to choose a team to play basketball. He will choose players from left to right, and the index of each chosen player (excluding the first one taken) will be strictly greater than the index of the previously chosen player. To avoid giving preference to one of the rows, Demid chooses students in such a way that no consecutive chosen students belong to the same row. The first student can be chosen among all $2n$ students (there are no additional constraints), and a team can consist of any number of students. 

Demid thinks, that in order to compose a perfect team, he should choose students in such a way, that the total height of all chosen students is maximum possible. Help Demid to find the maximum possible total height of players in a team he can choose.


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 10^5$) — the number of students in each row.

The second line of the input contains $n$ integers $h_{1, 1}, h_{1, 2}, \ldots, h_{1, n}$ ($1 \le h_{1, i} \le 10^9$), where $h_{1, i}$ is the height of the $i$-th student in the first row.

The third line of the input contains $n$ integers $h_{2, 1}, h_{2, 2}, \ldots, h_{2, n}$ ($1 \le h_{2, i} \le 10^9$), where $h_{2, i}$ is the height of the $i$-th student in the second row.


-----Output-----

Print a single integer — the maximum possible total height of players in a team Demid can choose.


-----Examples-----
Input
5
9 3 5 7 3
5 8 1 4 5

Output
29

Input
3
1 2 9
10 1 1

Output
19

Input
1
7
4

Output
7



-----Note-----

In the first example Demid can choose the following team as follows:  [Image] 

In the second example Demid can choose the following team as follows:  [Image]
user: Imagine that there is a group of three friends: A, B and С. A owes B 20 rubles and B owes C 20 rubles. The total sum of the debts is 40 rubles. You can see that the debts are not organized in a very optimal manner. Let's rearrange them like that: assume that A owes C 20 rubles and B doesn't owe anything to anybody. The debts still mean the same but the total sum of the debts now equals 20 rubles.

This task is a generalisation of a described example. Imagine that your group of friends has n people and you know the debts between the people. Optimize the given debts without changing their meaning. In other words, finally for each friend the difference between the total money he should give and the total money he should take must be the same. Print the minimum sum of all debts in the optimal rearrangement of the debts. See the notes to the test samples to better understand the problem.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 100; 0 ≤ m ≤ 10^4). The next m lines contain the debts. The i-th line contains three integers a_{i}, b_{i}, c_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}; 1 ≤ c_{i} ≤ 100), which mean that person a_{i} owes person b_{i} c_{i} rubles.

Assume that the people are numbered by integers from 1 to n.

It is guaranteed that the same pair of people occurs at most once in the input. The input doesn't simultaneously contain pair of people (x, y) and pair of people (y, x).


-----Output-----

Print a single integer — the minimum sum of debts in the optimal rearrangement.


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

Output
10

Input
3 0

Output
0

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

Output
0



-----Note-----

In the first sample, you can assume that person number 1 owes 8 rubles to person number 2, 1 ruble to person number 3 and 1 ruble to person number 4. He doesn't owe anybody else anything. In the end, the total debt equals 10.

In the second sample, there are no debts.

In the third sample, you can annul all the debts.
user: Mike and some bears are playing a game just for fun. Mike is the judge. All bears except Mike are standing in an n × m grid, there's exactly one bear in each cell. We denote the bear standing in column number j of row number i by (i, j). Mike's hands are on his ears (since he's the judge) and each bear standing in the grid has hands either on his mouth or his eyes. [Image] 

They play for q rounds. In each round, Mike chooses a bear (i, j) and tells him to change his state i. e. if his hands are on his mouth, then he'll put his hands on his eyes or he'll put his hands on his mouth otherwise. After that, Mike wants to know the score of the bears.

Score of the bears is the maximum over all rows of number of consecutive bears with hands on their eyes in that row.

Since bears are lazy, Mike asked you for help. For each round, tell him the score of these bears after changing the state of a bear selected in that round. 


-----Input-----

The first line of input contains three integers n, m and q (1 ≤ n, m ≤ 500 and 1 ≤ q ≤ 5000).

The next n lines contain the grid description. There are m integers separated by spaces in each line. Each of these numbers is either 0 (for mouth) or 1 (for eyes).

The next q lines contain the information about the rounds. Each of them contains two integers i and j (1 ≤ i ≤ n and 1 ≤ j ≤ m), the row number and the column number of the bear changing his state.


-----Output-----

After each round, print the current score of the bears.


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

Output
3
4
3
3
4
user: There is a long plate s containing n digits. Iahub wants to delete some digits (possibly none, but he is not allowed to delete all the digits) to form his "magic number" on the plate, a number that is divisible by 5. Note that, the resulting number may contain leading zeros.

Now Iahub wants to count the number of ways he can obtain magic number, modulo 1000000007 (10^9 + 7). Two ways are different, if the set of deleted positions in s differs.

Look at the input part of the statement, s is given in a special form.


-----Input-----

In the first line you're given a string a (1 ≤ |a| ≤ 10^5), containing digits only. In the second line you're given an integer k (1 ≤ k ≤ 10^9). The plate s is formed by concatenating k copies of a together. That is n = |a|·k.


-----Output-----

Print a single integer — the required number of ways modulo 1000000007 (10^9 + 7).


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

Output
4

Input
13990
2

Output
528

Input
555
2

Output
63



-----Note-----

In the first case, there are four possible ways to make a number that is divisible by 5: 5, 15, 25 and 125.

In the second case, remember to concatenate the copies of a. The actual plate is 1399013990.

In the third case, except deleting all digits, any choice will do. Therefore there are 2^6 - 1 = 63 possible ways to delete digits.
user: Thanos wants to destroy the avengers base, but he needs to destroy the avengers along with their base.

Let we represent their base with an array, where each position can be occupied by many avengers, but one avenger can occupy only one position. Length of their base is a perfect power of $2$. Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:   if the current length is at least $2$, divide the base into $2$ equal halves and destroy them separately, or  burn the current base. If it contains no avenger in it, it takes $A$ amount of power, otherwise it takes his $B \cdot n_a \cdot l$ amount of power, where $n_a$ is the number of avengers and $l$ is the length of the current base. Output the minimum power needed by Thanos to destroy the avengers' base.


-----Input-----

The first line contains four integers $n$, $k$, $A$ and $B$ ($1 \leq n \leq 30$, $1 \leq k \leq 10^5$, $1 \leq A,B \leq 10^4$), where $2^n$ is the length of the base, $k$ is the number of avengers and $A$ and $B$ are the constants explained in the question.

The second line contains $k$ integers $a_{1}, a_{2}, a_{3}, \ldots, a_{k}$ ($1 \leq a_{i} \leq 2^n$), where $a_{i}$ represents the position of avenger in the base.


-----Output-----

Output one integer — the minimum power needed to destroy the avengers base.


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

Output
6

Input
3 2 1 2
1 7

Output
8



-----Note-----

Consider the first example.

One option for Thanos is to burn the whole base $1-4$ with power $2 \cdot 2 \cdot 4 = 16$.

Otherwise he can divide the base into two parts $1-2$ and $3-4$.

For base $1-2$, he can either burn it with power $2 \cdot 1 \cdot 2 = 4$ or divide it into $2$ parts $1-1$ and $2-2$.

For base $1-1$, he can burn it with power $2 \cdot 1 \cdot 1 = 2$. For $2-2$, he can destroy it with power $1$, as there are no avengers. So, the total power for destroying $1-2$ is $2 + 1 = 3$, which is less than $4$. 

Similarly, he needs $3$ power to destroy $3-4$. The total minimum power needed is $6$.
user: In Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.

We will consider an extremely simplified subset of Python with only two types of statements.

Simple statements are written in a single line, one per line. An example of a simple statement is assignment.

For statements are compound statements: they contain one or several other statements. For statement consists of a header written in a separate line which starts with "for" prefix, and loop body. Loop body is a block of statements indented one level further than the header of the loop. Loop body can contain both types of statements. Loop body can't be empty.

You are given a sequence of statements without indentation. Find the number of ways in which the statements can be indented to form a valid Python program.


-----Input-----

The first line contains a single integer N (1 ≤ N ≤ 5000) — the number of commands in the program. N lines of the program follow, each line describing a single command. Each command is either "f" (denoting "for statement") or "s" ("simple statement"). It is guaranteed that the last line is a simple statement.


-----Output-----

Output one line containing an integer - the number of ways the given sequence of statements can be indented modulo 10^9 + 7. 


-----Examples-----
Input
4
s
f
f
s

Output
1

Input
4
f
s
f
s

Output
2



-----Note-----

In the first test case, there is only one way to indent the program: the second for statement must be part of the body of the first one.

simple statement

for statement

    for statement

        simple statement



In the second test case, there are two ways to indent the program: the second for statement can either be part of the first one's body or a separate statement following the first one.

for statement

    simple statement

    for statement

        simple statement



or

for statement

    simple statement

for statement

    simple statement
user: The city administration of IT City decided to fix up a symbol of scientific and technical progress in the city's main square, namely an indicator board that shows the effect of Moore's law in real time.

Moore's law is the observation that the number of transistors in a dense integrated circuit doubles approximately every 24 months. The implication of Moore's law is that computer performance as function of time increases exponentially as well.

You are to prepare information that will change every second to display on the indicator board. Let's assume that every second the number of transistors increases exactly 1.000000011 times.


-----Input-----

The only line of the input contains a pair of integers n (1000 ≤ n ≤ 10 000) and t (0 ≤ t ≤ 2 000 000 000) — the number of transistors in the initial time and the number of seconds passed since the initial time.


-----Output-----

Output one number — the estimate of the number of transistors in a dence integrated circuit in t seconds since the initial time. The relative error of your answer should not be greater than 10^{ - 6}.


-----Examples-----
Input
1000 1000000

Output
1011.060722383550382782399454922040
user: Joe has been hurt on the Internet. Now he is storming around the house, destroying everything in his path.

Joe's house has n floors, each floor is a segment of m cells. Each cell either contains nothing (it is an empty cell), or has a brick or a concrete wall (always something one of three). It is believed that each floor is surrounded by a concrete wall on the left and on the right.

Now Joe is on the n-th floor and in the first cell, counting from left to right. At each moment of time, Joe has the direction of his gaze, to the right or to the left (always one direction of the two). Initially, Joe looks to the right.

Joe moves by a particular algorithm. Every second he makes one of the following actions:   If the cell directly under Joe is empty, then Joe falls down. That is, he moves to this cell, the gaze direction is preserved.  Otherwise consider the next cell in the current direction of the gaze.   If the cell is empty, then Joe moves into it, the gaze direction is preserved.  If this cell has bricks, then Joe breaks them with his forehead (the cell becomes empty), and changes the direction of his gaze to the opposite.  If this cell has a concrete wall, then Joe just changes the direction of his gaze to the opposite (concrete can withstand any number of forehead hits).  

Joe calms down as soon as he reaches any cell of the first floor.

The figure below shows an example Joe's movements around the house.

 [Image] 

Determine how many seconds Joe will need to calm down.


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 10^4).

Next n lines contain the description of Joe's house. The i-th of these lines contains the description of the (n - i + 1)-th floor of the house — a line that consists of m characters: "." means an empty cell, "+" means bricks and "#" means a concrete wall.

It is guaranteed that the first cell of the n-th floor is empty.


-----Output-----

Print a single number — the number of seconds Joe needs to reach the first floor; or else, print word "Never" (without the quotes), if it can never happen.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
3 5
..+.#
#+..+
+.#+.

Output
14
Input
4 10
...+.##+.+
+#++..+++#
++.#++++..
.+##.++#.+

Output
42

Input
2 2
..
++

Output
Never