meetforever/GRPO_CL huggingface dataset:
user: Nura wants to buy k gadgets. She has only s burles for that. She can buy each gadget for dollars or for pounds. So each gadget is selling only for some type of currency. The type of currency and the cost in that currency are not changing.

Nura can buy gadgets for n days. For each day you know the exchange rates of dollar and pound, so you know the cost of conversion burles to dollars or to pounds.

Each day (from 1 to n) Nura can buy some gadgets by current exchange rate. Each day she can buy any gadgets she wants, but each gadget can be bought no more than once during n days.

Help Nura to find the minimum day index when she will have k gadgets. Nura always pays with burles, which are converted according to the exchange rate of the purchase day. Nura can't buy dollars or pounds, she always stores only burles. Gadgets are numbered with integers from 1 to m in order of their appearing in input.


-----Input-----

First line contains four integers n, m, k, s (1 ≤ n ≤ 2·10^5, 1 ≤ k ≤ m ≤ 2·10^5, 1 ≤ s ≤ 10^9) — number of days, total number and required number of gadgets, number of burles Nura has.

Second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6) — the cost of one dollar in burles on i-th day.

Third line contains n integers b_{i} (1 ≤ b_{i} ≤ 10^6) — the cost of one pound in burles on i-th day.

Each of the next m lines contains two integers t_{i}, c_{i} (1 ≤ t_{i} ≤ 2, 1 ≤ c_{i} ≤ 10^6) — type of the gadget and it's cost. For the gadgets of the first type cost is specified in dollars. For the gadgets of the second type cost is specified in pounds.


-----Output-----

If Nura can't buy k gadgets print the only line with the number -1.

Otherwise the first line should contain integer d — the minimum day index, when Nura will have k gadgets. On each of the next k lines print two integers q_{i}, d_{i} — the number of gadget and the day gadget should be bought. All values q_{i} should be different, but the values d_{i} can coincide (so Nura can buy several gadgets at one day). The days are numbered from 1 to n.

In case there are multiple possible solutions, print any of them.


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

Output
3
1 1
2 3

Input
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2

Output
-1

Input
4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432

Output
-1
user: Ohana Matsumae is trying to clean a room, which is divided up into an n by n grid of squares. Each square is initially either clean or dirty. Ohana can sweep her broom over columns of the grid. Her broom is very strange: if she sweeps over a clean square, it will become dirty, and if she sweeps over a dirty square, it will become clean. She wants to sweep some columns of the room to maximize the number of rows that are completely clean. It is not allowed to sweep over the part of the column, Ohana can only sweep the whole column.

Return the maximum number of rows that she can make completely clean.


-----Input-----

The first line of input will be a single integer n (1 ≤ n ≤ 100).

The next n lines will describe the state of the room. The i-th line will contain a binary string with n characters denoting the state of the i-th row of the room. The j-th character on this line is '1' if the j-th square in the i-th row is clean, and '0' if it is dirty.


-----Output-----

The output should be a single line containing an integer equal to a maximum possible number of rows that are completely clean.


-----Examples-----
Input
4
0101
1000
1111
0101

Output
2

Input
3
111
111
111

Output
3



-----Note-----

In the first sample, Ohana can sweep the 1st and 3rd columns. This will make the 1st and 4th row be completely clean.

In the second sample, everything is already clean, so Ohana doesn't need to do anything.
user: There are n servers in a laboratory, each of them can perform tasks. Each server has a unique id — integer from 1 to n.

It is known that during the day q tasks will come, the i-th of them is characterized with three integers: t_{i} — the moment in seconds in which the task will come, k_{i} — the number of servers needed to perform it, and d_{i} — the time needed to perform this task in seconds. All t_{i} are distinct.

To perform the i-th task you need k_{i} servers which are unoccupied in the second t_{i}. After the servers begin to perform the task, each of them will be busy over the next d_{i} seconds. Thus, they will be busy in seconds t_{i}, t_{i} + 1, ..., t_{i} + d_{i} - 1. For performing the task, k_{i} servers with the smallest ids will be chosen from all the unoccupied servers. If in the second t_{i} there are not enough unoccupied servers, the task is ignored.

Write the program that determines which tasks will be performed and which will be ignored.


-----Input-----

The first line contains two positive integers n and q (1 ≤ n ≤ 100, 1 ≤ q ≤ 10^5) — the number of servers and the number of tasks. 

Next q lines contains three integers each, the i-th line contains integers t_{i}, k_{i} and d_{i} (1 ≤ t_{i} ≤ 10^6, 1 ≤ k_{i} ≤ n, 1 ≤ d_{i} ≤ 1000) — the moment in seconds in which the i-th task will come, the number of servers needed to perform it, and the time needed to perform this task in seconds. The tasks are given in a chronological order and they will come in distinct seconds. 


-----Output-----

Print q lines. If the i-th task will be performed by the servers, print in the i-th line the sum of servers' ids on which this task will be performed. Otherwise, print -1.


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

Output
6
-1
10

Input
3 2
3 2 3
5 1 2

Output
3
3

Input
8 6
1 3 20
4 2 1
6 5 5
10 1 1
15 3 6
21 8 8

Output
6
9
30
-1
15
36



-----Note-----

In the first example in the second 1 the first task will come, it will be performed on the servers with ids 1, 2 and 3 (the sum of the ids equals 6) during two seconds. In the second 2 the second task will come, it will be ignored, because only the server 4 will be unoccupied at that second. In the second 3 the third task will come. By this time, servers with the ids 1, 2 and 3 will be unoccupied again, so the third task will be done on all the servers with the ids 1, 2, 3 and 4 (the sum of the ids is 10).

In the second example in the second 3 the first task will come, it will be performed on the servers with ids 1 and 2 (the sum of the ids is 3) during three seconds. In the second 5 the second task will come, it will be performed on the server 3, because the first two servers will be busy performing the first task.
user: Consider 2n rows of the seats in a bus. n rows of the seats on the left and n rows of the seats on the right. Each row can be filled by two people. So the total capacity of the bus is 4n.

Consider that m (m ≤ 4n) people occupy the seats in the bus. The passengers entering the bus are numbered from 1 to m (in the order of their entering the bus). The pattern of the seat occupation is as below:

1-st row left window seat, 1-st row right window seat, 2-nd row left window seat, 2-nd row right window seat, ... , n-th row left window seat, n-th row right window seat.

After occupying all the window seats (for m > 2n) the non-window seats are occupied:

1-st row left non-window seat, 1-st row right non-window seat, ... , n-th row left non-window seat, n-th row right non-window seat.

All the passengers go to a single final destination. In the final destination, the passengers get off in the given order.

1-st row left non-window seat, 1-st row left window seat, 1-st row right non-window seat, 1-st row right window seat, ... , n-th row left non-window seat, n-th row left window seat, n-th row right non-window seat, n-th row right window seat. [Image] The seating for n = 9 and m = 36. 

You are given the values n and m. Output m numbers from 1 to m, the order in which the passengers will get off the bus.


-----Input-----

The only line contains two integers, n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 4n) — the number of pairs of rows and the number of passengers.


-----Output-----

Print m distinct integers from 1 to m — the order in which the passengers will get off the bus.


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

Output
5 1 6 2 7 3 4

Input
9 36

Output
19 1 20 2 21 3 22 4 23 5 24 6 25 7 26 8 27 9 28 10 29 11 30 12 31 13 32 14 33 15 34 16 35 17 36 18
user: Как известно, в теплую погоду многие жители крупных городов пользуются сервисами городского велопроката. Вот и Аркадий сегодня будет добираться от школы до дома, используя городские велосипеды.

Школа и дом находятся на одной прямой улице, кроме того, на той же улице есть n точек, где можно взять велосипед в прокат или сдать его. Первый велопрокат находится в точке x_1 километров вдоль улицы, второй — в точке x_2 и так далее, n-й велопрокат находится в точке x_{n}. Школа Аркадия находится в точке x_1 (то есть там же, где и первый велопрокат), а дом — в точке x_{n} (то есть там же, где и n-й велопрокат). Известно, что x_{i} < x_{i} + 1 для всех 1 ≤ i < n.

Согласно правилам пользования велопроката, Аркадий может брать велосипед в прокат только на ограниченное время, после этого он должен обязательно вернуть его в одной из точек велопроката, однако, он тут же может взять новый велосипед, и отсчет времени пойдет заново. Аркадий может брать не более одного велосипеда в прокат одновременно. Если Аркадий решает взять велосипед в какой-то точке проката, то он сдаёт тот велосипед, на котором он до него доехал, берёт ровно один новый велосипед и продолжает на нём своё движение.

За отведенное время, независимо от выбранного велосипеда, Аркадий успевает проехать не больше k километров вдоль улицы. 

Определите, сможет ли Аркадий доехать на велосипедах от школы до дома, и если да, то какое минимальное число раз ему необходимо будет взять велосипед в прокат, включая первый велосипед? Учтите, что Аркадий не намерен сегодня ходить пешком.


-----Входные данные-----

В первой строке следуют два целых числа n и k (2 ≤ n ≤ 1 000, 1 ≤ k ≤ 100 000) — количество велопрокатов и максимальное расстояние, которое Аркадий может проехать на одном велосипеде.

В следующей строке следует последовательность целых чисел x_1, x_2, ..., x_{n} (0 ≤ x_1 < x_2 < ... < x_{n} ≤ 100 000) — координаты точек, в которых находятся велопрокаты. Гарантируется, что координаты велопрокатов заданы в порядке возрастания.


-----Выходные данные-----

Если Аркадий не сможет добраться от школы до дома только на велосипедах, выведите -1. В противном случае, выведите минимальное количество велосипедов, которые Аркадию нужно взять в точках проката.


-----Примеры-----
Входные данные
4 4
3 6 8 10

Выходные данные
2

Входные данные
2 9
10 20

Выходные данные
-1

Входные данные
12 3
4 6 7 9 10 11 13 15 17 18 20 21

Выходные данные
6



-----Примечание-----

В первом примере Аркадий должен взять первый велосипед в первом велопрокате и доехать на нём до второго велопроката. Во втором велопрокате он должен взять новый велосипед, на котором он сможет добраться до четвертого велопроката, рядом с которым и находится его дом. Поэтому Аркадию нужно всего два велосипеда, чтобы добраться от школы до дома.

Во втором примере всего два велопроката, расстояние между которыми 10. Но максимальное расстояние, которое можно проехать на одном велосипеде, равно 9. Поэтому Аркадий не сможет добраться от школы до дома только на велосипедах.
user: Tavas is a strange creature. Usually "zzz" comes out of people's mouth while sleeping, but string s of length n comes out from Tavas' mouth instead. [Image] 

Today Tavas fell asleep in Malekas' place. While he was sleeping, Malekas did a little process on s. Malekas has a favorite string p. He determined all positions x_1 < x_2 < ... < x_{k} where p matches s. More formally, for each x_{i} (1 ≤ i ≤ k) he condition s_{x}_{i}s_{x}_{i} + 1... s_{x}_{i} + |p| - 1 = p is fullfilled.

Then Malekas wrote down one of subsequences of x_1, x_2, ... x_{k} (possibly, he didn't write anything) on a piece of paper. Here a sequence b is a subsequence of sequence a if and only if we can turn a into b by removing some of its elements (maybe no one of them or all).

After Tavas woke up, Malekas told him everything. He couldn't remember string s, but he knew that both p and s only contains lowercase English letters and also he had the subsequence he had written on that piece of paper.

Tavas wonders, what is the number of possible values of s? He asked SaDDas, but he wasn't smart enough to solve this. So, Tavas asked you to calculate this number for him.

Answer can be very large, so Tavas wants you to print the answer modulo 10^9 + 7.


-----Input-----

The first line contains two integers n and m, the length of s and the length of the subsequence Malekas wrote down (1 ≤ n ≤ 10^6 and 0 ≤ m ≤ n - |p| + 1).

The second line contains string p (1 ≤ |p| ≤ n).

The next line contains m space separated integers y_1, y_2, ..., y_{m}, Malekas' subsequence (1 ≤ y_1 < y_2 < ... < y_{m} ≤ n - |p| + 1).


-----Output-----

In a single line print the answer modulo 1000 000 007.


-----Examples-----
Input
6 2
ioi
1 3

Output
26

Input
5 2
ioi
1 2

Output
0



-----Note-----

In the first sample test all strings of form "ioioi?" where the question mark replaces arbitrary English letter satisfy.

Here |x| denotes the length of string x.

Please note that it's possible that there is no such string (answer is 0).
user: [Image] 


-----Input-----

The input contains a single integer $a$ ($0 \le a \le 15$).


-----Output-----

Output a single integer.


-----Example-----
Input
3

Output
13
user: Acingel is a small town. There was only one doctor here — Miss Ada. She was very friendly and nobody has ever said something bad about her, so who could've expected that Ada will be found dead in her house? Mr Gawry, world-famous detective, is appointed to find the criminal. He asked $m$ neighbours of Ada about clients who have visited her in that unlucky day. Let's number the clients from $1$ to $n$. Each neighbour's testimony is a permutation of these numbers, which describes the order in which clients have been seen by the asked neighbour.

However, some facts are very suspicious – how it is that, according to some of given permutations, some client has been seen in the morning, while in others he has been seen in the evening? "In the morning some of neighbours must have been sleeping!" — thinks Gawry — "and in the evening there's been too dark to see somebody's face...". Now he wants to delete some prefix and some suffix (both prefix and suffix can be empty) in each permutation, so that they'll be non-empty and equal to each other after that — some of the potential criminals may disappear, but the testimony won't stand in contradiction to each other.

In how many ways he can do it? Two ways are called different if the remaining common part is different.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $1 \le m \le 10$) — the number of suspects and the number of asked neighbors.

Each of the next $m$ lines contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). It is guaranteed that these integers form a correct permutation (that is, each number from $1$ to $n$ appears exactly once).


-----Output-----

Output a single integer denoting the number of ways to delete some prefix and some suffix of each permutation (possibly empty), such that the remaining parts will be equal and non-empty.


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

Output
4

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

Output
5

Input
2 2
1 2
2 1

Output
2



-----Note-----

In the first example, all possible common parts are $[1]$, $[2]$, $[3]$ and $[2, 3]$.

In the second and third examples, you can only leave common parts of length $1$.
user: You are given two lists of segments $[al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n]$ and $[bl_1, br_1], [bl_2, br_2], \dots, [bl_n, br_n]$.

Initially, all segments $[al_i, ar_i]$ are equal to $[l_1, r_1]$ and all segments $[bl_i, br_i]$ are equal to $[l_2, r_2]$.

In one step, you can choose one segment (either from the first or from the second list) and extend it by $1$. In other words, suppose you've chosen segment $[x, y]$ then you can transform it either into $[x - 1, y]$ or into $[x, y + 1]$.

Let's define a total intersection $I$ as the sum of lengths of intersections of the corresponding pairs of segments, i.e. $\sum\limits_{i=1}^{n}{\text{intersection_length}([al_i, ar_i], [bl_i, br_i])}$. Empty intersection has length $0$ and length of a segment $[x, y]$ is equal to $y - x$.

What is the minimum number of steps you need to make $I$ greater or equal to $k$?


-----Input-----

The first line contains the single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^9$) — the length of lists and the minimum required total intersection.

The second line of each test case contains two integers $l_1$ and $r_1$ ($1 \le l_1 \le r_1 \le 10^9$) — the segment all $[al_i, ar_i]$ are equal to initially.

The third line of each test case contains two integers $l_2$ and $r_2$ ($1 \le l_2 \le r_2 \le 10^9$) — the segment all $[bl_i, br_i]$ are equal to initially.

It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $t$ integers — one per test case. For each test case, print the minimum number of step you need to make $I$ greater or equal to $k$.


-----Example-----
Input
3
3 5
1 2
3 4
2 1000000000
1 1
999999999 999999999
10 3
5 10
7 8

Output
7
2000000000
0



-----Note-----

In the first test case, we can achieve total intersection $5$, for example, using next strategy:   make $[al_1, ar_1]$ from $[1, 2]$ to $[1, 4]$ in $2$ steps;  make $[al_2, ar_2]$ from $[1, 2]$ to $[1, 3]$ in $1$ step;  make $[bl_1, br_1]$ from $[3, 4]$ to $[1, 4]$ in $2$ steps;  make $[bl_2, br_2]$ from $[3, 4]$ to $[1, 4]$ in $2$ steps.  In result, $I = \text{intersection_length}([al_1, ar_1], [bl_1, br_1]) + \text{intersection_length}([al_2, ar_2], [bl_2, br_2]) + \\ + \text{intersection_length}([al_3, ar_3], [bl_3, br_3]) = 3 + 2 + 0 = 5$

In the second test case, we can make $[al_1, ar_1] = [0, 1000000000]$ in $1000000000$ steps and $[bl_1, br_1] = [0, 1000000000]$ in $1000000000$ steps.

In the third test case, the total intersection $I$ is already equal to $10 > 3$, so we don't need to do any steps.
user: Petya has recently started working as a programmer in the IT city company that develops computer games.

Besides game mechanics implementation to create a game it is necessary to create tool programs that can be used by game designers to create game levels. Petya's first assignment is to create a tool that allows to paint different arrows on the screen.

A user of this tool will choose a point on the screen, specify a vector (the arrow direction) and vary several parameters to get the required graphical effect. In the first version of the program Petya decided to limit parameters of the arrow by the following: a point with coordinates (px, py), a nonzero vector with coordinates (vx, vy), positive scalars a, b, c, d, a > c.

The produced arrow should have the following properties. The arrow consists of a triangle and a rectangle. The triangle is isosceles with base of length a and altitude of length b perpendicular to the base. The rectangle sides lengths are c and d. Point (px, py) is situated in the middle of the triangle base and in the middle of side of rectangle that has length c. Area of intersection of the triangle and the rectangle is zero. The direction from (px, py) point to the triangle vertex opposite to base containing the point coincides with direction of (vx, vy) vector.

Enumerate the arrow points coordinates in counter-clockwise order starting from the tip.

 [Image] 


-----Input-----

The only line of the input contains eight integers px, py, vx, vy ( - 1000 ≤ px, py, vx, vy ≤ 1000, vx^2 + vy^2 > 0), a, b, c, d (1 ≤ a, b, c, d ≤ 1000, a > c).


-----Output-----

Output coordinates of the arrow points in counter-clockwise order. Each line should contain two coordinates, first x, then y. Relative or absolute error should not be greater than 10^{ - 9}.


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

Output
8.000000000000 11.000000000000
4.000000000000 8.000000000000
6.000000000000 8.000000000000
6.000000000000 3.000000000000
10.000000000000 3.000000000000
10.000000000000 8.000000000000
12.000000000000 8.000000000000
user: You are given an array a of length n. We define f_{a} the following way:

  Initially f_{a} = 0, M = 1;  for every 2 ≤ i ≤ n if a_{M} < a_{i} then we set f_{a} = f_{a} + a_{M} and then set M = i. 

Calculate the sum of f_{a} over all n! permutations of the array a modulo 10^9 + 7.

Note: two elements are considered different if their indices differ, so for every array a there are exactly n! permutations.


-----Input-----

The first line contains integer n (1 ≤ n ≤  1 000 000) — the size of array a.

Second line contains n integers a_1, a_2, ..., a_{n} (1 ≤  a_{i} ≤  10^9).


-----Output-----

Print the only integer, the sum of f_{a} over all n! permutations of the array a modulo 10^9 + 7.


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

Output
1
Input
3
1 1 2

Output
4


-----Note-----

For the second example all the permutations are:

  p = [1, 2, 3] : f_{a} is equal to 1;  p = [1, 3, 2] : f_{a} is equal to 1;  p = [2, 1, 3] : f_{a} is equal to 1;  p = [2, 3, 1] : f_{a} is equal to 1;  p = [3, 1, 2] : f_{a} is equal to 0;  p = [3, 2, 1] : f_{a} is equal to 0. 

Where p is the array of the indices of initial array a. The sum of f_{a} is equal to 4.
user: [Image] 

It's the end of July – the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it's a necessity to not let any uninvited guests in.

There are 26 entrances in Jelly Castle, enumerated with uppercase English letters from A to Z. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest's arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously.

For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There are k such guards in the castle, so if there are more than k opened doors, one of them is going to be left unguarded! Notice that a guard can't leave his post until the door he is assigned to is closed.

Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more than k doors were opened.


-----Input-----

Two integers are given in the first string: the number of guests n and the number of guards k (1 ≤ n ≤ 10^6, 1 ≤ k ≤ 26).

In the second string, n uppercase English letters s_1s_2... s_{n} are given, where s_{i} is the entrance used by the i-th guest.


-----Output-----

Output «YES» if at least one door was unguarded during some time, and «NO» otherwise.

You can output each letter in arbitrary case (upper or lower).


-----Examples-----
Input
5 1
AABBB

Output
NO

Input
5 1
ABABB

Output
YES



-----Note-----

In the first sample case, the door A is opened right before the first guest's arrival and closed when the second guest enters the castle. The door B is opened right before the arrival of the third guest, and closed after the fifth one arrives. One guard can handle both doors, as the first one is closed before the second one is opened.

In the second sample case, the door B is opened before the second guest's arrival, but the only guard can't leave the door A unattended, as there is still one more guest that should enter the castle through this door.