vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The legendary Farmer John is throwing a huge party, and animals from all over the world are hanging out at his house. His guests are hungry, so he instructs his cow Bessie to bring out the snacks! Moo!

There are $n$ snacks flavors, numbered with integers $1, 2, \ldots, n$. Bessie has $n$ snacks, one snack of each flavor. Every guest has exactly two favorite flavors. The procedure for eating snacks will go as follows:  First, Bessie will line up the guests in some way.  Then in this order, guests will approach the snacks one by one.  Each guest in their turn will eat all remaining snacks of their favorite flavor. In case no favorite flavors are present when a guest goes up, they become very sad.  

Help Bessie to minimize the number of sad guests by lining the guests in an optimal way.


-----Input-----

The first line contains integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le 10^5$), the number of snacks and the number of guests. 

The $i$-th of the following $k$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$), favorite snack flavors of the $i$-th guest.


-----Output-----

Output one integer, the smallest possible number of sad guests.


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

Output
1

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

Output
0



-----Note-----

In the first example, Bessie can order the guests like this: $3, 1, 2, 4$. Guest $3$ goes first and eats snacks $1$ and $4$. Then the guest $1$ goes and eats the snack $2$ only, because the snack $1$ has already been eaten. Similarly, the guest $2$ goes up and eats the snack $3$ only. All the snacks are gone, so the guest $4$ will be sad. 

In the second example, one optimal ordering is $2, 1, 3, 5, 4$. All the guests will be satisfied.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Inna and Alarm Clock

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Inna loves sleeping very much, so she needs *n* alarm clocks in total to wake up. Let's suppose that Inna's room is a 100<=×<=100 square with the lower left corner at point (0,<=0) and with the upper right corner at point (100,<=100). Then the alarm clocks are points with integer coordinates in this square.

The morning has come. All *n* alarm clocks in Inna's room are ringing, so Inna wants to turn them off. For that Inna has come up with an amusing game:
 -  First Inna chooses a type of segments that she will use throughout the game. The segments can be either vertical or horizontal. -  Then Inna makes multiple moves. In a single move, Inna can paint a segment of any length on the plane, she chooses its type at the beginning of the game (either vertical or horizontal), then all alarm clocks that are on this segment switch off. The game ends when all the alarm clocks are switched off. 
Inna is very sleepy, so she wants to get through the alarm clocks as soon as possible. Help her, find the minimum number of moves in the game that she needs to turn off all the alarm clocks!

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of the alarm clocks. The next *n* lines describe the clocks: the *i*-th line contains two integers *x**i*, *y**i* — the coordinates of the *i*-th alarm clock (0<=≤<=*x**i*,<=*y**i*<=≤<=100).

Note that a single point in the room can contain any number of alarm clocks and the alarm clocks can lie on the sides of the square that represents the room.

Output Specification:
In a single line print a single integer — the minimum number of segments Inna will have to draw if she acts optimally.

Demo Input:
['4\n0 0\n0 1\n0 2\n1 0\n', '4\n0 0\n0 1\n1 0\n1 1\n', '4\n1 1\n1 2\n2 3\n3 3\n']

Demo Output:
['2\n', '2\n', '3\n']

Note:
In the first sample, Inna first chooses type "vertical segments", and then she makes segments with ends at : (0, 0), (0, 2); and, for example, (1, 0), (1, 1). If she paints horizontal segments, she will need at least 3 segments.

In the third sample it is important to note that Inna doesn't have the right to change the type of the segments during the game. That's why she will need 3 horizontal or 3 vertical segments to end the game.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an n × m rectangle table, its cells are not initially painted. Your task is to paint all cells of the table. The resulting picture should be a tiling of the table with squares. More formally:  each cell must be painted some color (the colors are marked by uppercase Latin letters);  we will assume that two cells of the table are connected if they are of the same color and share a side; each connected region of the table must form a square. 

Given n and m, find lexicographically minimum coloring of the table that meets the described properties.


-----Input-----

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


-----Output-----

Print lexicographically minimum coloring of the table that meets the described conditions. 

One coloring (let's call it X) is considered lexicographically less than the other one (let's call it Y), if:  consider all the table cells from left to right and from top to bottom (first, the first cell in the first row, then the second cell in the first row and so on);  let's find in this order the first cell that has distinct colors in two colorings;  the letter that marks the color of the cell in X, goes alphabetically before the letter that marks the color of the cell in Y. 


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

Output
ABA

Input
2 2

Output
AA
AA

Input
3 4

Output
AAAB
AAAC
AAAB

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Fancy Number

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A car number in Berland consists of exactly *n* digits. A number is called beautiful if it has at least *k* equal digits. Vasya wants to change the digits in his car's number so that the number became beautiful. To replace one of *n* digits Vasya has to pay the sum of money, equal to the absolute difference between the old digit and the new one.

Help Vasya: find the minimum sum of money he should pay to make the number of his car beautiful. You should also find the resulting beautiful number. If there are several such numbers, then print the lexicographically minimum one.

Input Specification:
The first line contains two space-separated integers *n* and *k* (2<=≤<=*n*<=≤<=104,<=2<=≤<=*k*<=≤<=*n*) which represent how many digits the number has and how many equal digits a beautiful number should have. The second line consists of *n* digits. It describes the old number of Vasya's car. It is guaranteed that the number contains no spaces and only contains digits.

Output Specification:
On the first line print the minimum sum of money Vasya needs to change the number. On the second line print the car's new number. If there are several solutions, print the lexicographically minimum one.

Demo Input:
['6 5\n898196\n', '3 2\n533\n', '10 6\n0001112223\n']

Demo Output:
['4\n888188\n', '0\n533\n', '3\n0000002223\n']

Note:
In the first sample replacing the second digit with an "8" costs |9 - 8| = 1. Replacing the fifth digit with an "8" costs the same. Replacing the sixth digit costs |6 - 8| = 2. As a result, Vasya will pay 1 + 1 + 2 = 4 for a beautiful number "888188".

The lexicographical comparison of strings is performed by the &lt; operator in modern programming languages. The string *x* is lexicographically smaller than the string *y*, if there exists such *i* (1 ≤ *i* ≤ *n*), that *x*<sub class="lower-index">*i*</sub> &lt; *y*<sub class="lower-index">*i*</sub>, and for any *j* (1 ≤ *j* &lt; *i*) *x*<sub class="lower-index">*j*</sub> = *y*<sub class="lower-index">*j*</sub>. The strings compared in this problem will always have the length *n*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yuezheng Ling gives Luo Tianyi a tree which has n nodes, rooted at 1. 

Luo Tianyi will tell you that the parent of the i-th node is a_i (1 ≤ a_i<i for 2 ≤ i ≤ n), and she will ask you to perform q queries of 2 types:

  1. She'll give you three integers l, r and x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5). You need to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.
  2. She'll give you two integers u, v (1 ≤ u, v ≤ n). You need to find the [LCA](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of nodes u and v (their lowest common ancestor).

Input

The first line contains two integers n and q (2≤ n,q ≤ 10^5) — the number of nodes and the number of queries, respectively.

The second line contains n-1 integers a_2, a_3,..., a_n (1 ≤ a_i < i), where a_i is the parent of the node i.

Next q lines contain queries. For each query, the first integer of each line is t (t = 1 or 2) — the type of the query. 

If t = 1, this represents the query of the first type. Then, three integers will follow: l, r, x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5), meaning that you have to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.

If t = 2, this represents the query of the second type. Then, two integers will follow: u and v (1 ≤ u, v ≤ n), and you have to find the LCA of u and v. 

It's guaranteed that there is at least one query of the second type.

Output

For each query of the second type output answer on a new line.

Example

Input


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


Output


3
3
1

Note

The tree in example is shown below.

<image>

After the query of the first type, the tree changes and is looking as shown below.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While most students still sit their exams, the tractor college has completed the summer exam session. In fact, students study only one subject at this college — the Art of Operating a Tractor. Therefore, at the end of a term a student gets only one mark, a three (satisfactory), a four (good) or a five (excellent). Those who score lower marks are unfortunately expelled.

The college has n students, and oddly enough, each of them can be on scholarship. The size of the scholarships varies each term. Since the end-of-the-term exam has just ended, it's time to determine the size of the scholarship to the end of next term.

The monthly budget for the scholarships of the Tractor college is s rubles. To distribute the budget optimally, you must follow these rules:

  * The students who received the same mark for the exam, should receive the same scholarship;
  * Let us denote the size of the scholarship (in roubles) for students who have received marks 3, 4 and 5 for the exam, as k3, k4 and k5, respectively. The values k3, k4 and k5 must be integers and satisfy the inequalities 0 ≤ k3 ≤ k4 ≤ k5;
  * Let's assume that c3, c4, c5 show how many students received marks 3, 4 and 5 for the exam, respectively. The budget of the scholarship should be fully spent on them, that is, c3·k3 + c4·k4 + c5·k5 = s;
  * Let's introduce function <image> — the value that shows how well the scholarships are distributed between students. In the optimal distribution function f(k3, k4, k5) takes the minimum possible value. 



Given the results of the exam, and the budget size s, you have to find the optimal distribution of the scholarship.

Input

The first line has two integers n, s (3 ≤ n ≤ 300, 1 ≤ s ≤ 3·105) — the number of students and the budget size for the scholarship, respectively. The second line contains n integers, where the i-th number represents the mark that the i-th student got for the exam. It is guaranteed that at each mark was given to at least one student.

Output

On a single line print three integers k3, k4 and k5 — the sought values that represent the optimal distribution of the scholarships. If there are multiple optimal answers, print any of them. If there is no answer, print -1.

Examples

Input

5 11
3 4 3 5 5


Output

1 3 3


Input

6 15
5 3 3 4 4 5


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Simple Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Misha and Andrew were playing a very simple game. First, each player chooses an integer in the range from 1 to *n*. Let's assume that Misha chose number *m*, and Andrew chose number *a*.

Then, by using a random generator they choose a random integer *c* in the range between 1 and *n* (any integer from 1 to *n* is chosen with the same probability), after which the winner is the player, whose number was closer to *c*. The boys agreed that if *m* and *a* are located on the same distance from *c*, Misha wins.

Andrew wants to win very much, so he asks you to help him. You know the number selected by Misha, and number *n*. You need to determine which value of *a* Andrew must choose, so that the probability of his victory is the highest possible.

More formally, you need to find such integer *a* (1<=≤<=*a*<=≤<=*n*), that the probability that  is maximal, where *c* is the equiprobably chosen integer from 1 to *n* (inclusive).

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*m*<=≤<=*n*<=≤<=109) — the range of numbers in the game, and the number selected by Misha respectively.

Output Specification:
Print a single number — such value *a*, that probability that Andrew wins is the highest. If there are multiple such values, print the minimum of them.

Demo Input:
['3 1\n', '4 3\n']

Demo Output:
['2', '2']

Note:
In the first sample test: Andrew wins if *c* is equal to 2 or 3. The probability that Andrew wins is 2 / 3. If Andrew chooses *a* = 3, the probability of winning will be 1 / 3. If *a* = 1, the probability of winning is 0.

In the second sample test: Andrew wins if *c* is equal to 1 and 2. The probability that Andrew wins is 1 / 2. For other choices of *a* the probability of winning is less.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a closed world and a set of features that are defined for all the objects in the world. Each feature can be answered with "yes" or "no". Using those features, we can identify any object from the rest of the objects in the world. In other words, each object can be represented as a fixed-length sequence of booleans. Any object is different from other objects by at least one feature.

You would like to identify an object from others. For this purpose, you can ask a series of questions to someone who knows what the object is. Every question you can ask is about one of the features. He/she immediately answers each question with "yes" or "no" correctly. You can choose the next question after you get the answer to the previous question.

You kindly pay the answerer 100 yen as a tip for each question. Because you don' t have surplus money, it is necessary to minimize the number of questions in the worst case. You don’t know what is the correct answer, but fortunately know all the objects in the world. Therefore, you can plan an optimal strategy before you start questioning.

The problem you have to solve is: given a set of boolean-encoded objects, minimize the maximum number of questions by which every object in the set is identifiable.



Input

The input is a sequence of multiple datasets. Each dataset begins with a line which consists of two integers, m and n: the number of features, and the number of objects, respectively. You can assume 0 < m ≤ 11 and 0 < n ≤ 128. It is followed by n lines, each of which corresponds to an object. Each line includes a binary string of length m which represent the value ("yes" or "no") of features. There are no two identical objects.

The end of the input is indicated by a line containing two zeros. There are at most 100 datasets.

Output

For each dataset, minimize the maximum number of questions by which every object is identifiable and output the result.

Example

Input

8 1
11010101
11 4
00111001100
01001101011
01010000011
01100110001
11 16
01000101111
01011000000
01011111001
01101101001
01110010111
01110100111
10000001010
10010001000
10010110100
10100010100
10101010110
10110100010
11001010011
11011001001
11111000111
11111011101
11 12
10000000000
01000000000
00100000000
00010000000
00001000000
00000100000
00000010000
00000001000
00000000100
00000000010
00000000001
00000000000
9 32
001000000
000100000
000010000
000001000
000000100
000000010
000000001
000000000
011000000
010100000
010010000
010001000
010000100
010000010
010000001
010000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
100000000
111000000
110100000
110010000
110001000
110000100
110000010
110000001
110000000
0 0


Output

0
2
4
11
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nanami likes playing games, and is also really good at it. This day she was playing a new game which involved operating a power plant. Nanami's job is to control the generators in the plant and produce maximum output.

There are n generators in the plant. Each generator should be set to a generating level. Generating level is an integer (possibly zero or negative), the generating level of the i-th generator should be between li and ri (both inclusive). The output of a generator can be calculated using a certain quadratic function f(x), where x is the generating level of the generator. Each generator has its own function, the function of the i-th generator is denoted as fi(x).

However, there are m further restrictions to the generators. Let the generating level of the i-th generator be xi. Each restriction is of the form xu ≤ xv + d, where u and v are IDs of two different generators and d is an integer.

Nanami found the game tedious but giving up is against her creed. So she decided to have a program written to calculate the answer for her (the maximum total output of generators). Somehow, this became your job.

Input

The first line contains two integers n and m (1 ≤ n ≤ 50; 0 ≤ m ≤ 100) — the number of generators and the number of restrictions.

Then follow n lines, each line contains three integers ai, bi, and ci (|ai| ≤ 10; |bi|, |ci| ≤ 1000) — the coefficients of the function fi(x). That is, fi(x) = aix2 + bix + ci.

Then follow another n lines, each line contains two integers li and ri ( - 100 ≤ li ≤ ri ≤ 100).

Then follow m lines, each line contains three integers ui, vi, and di (1 ≤ ui, vi ≤ n; ui ≠ vi; |di| ≤ 200), describing a restriction. The i-th restriction is xui ≤ xvi + di.

Output

Print a single line containing a single integer — the maximum output of all the generators. It is guaranteed that there exists at least one valid configuration.

Examples

Input

3 3
0 1 0
0 1 1
0 1 2
0 3
1 2
-100 100
1 2 0
2 3 0
3 1 0


Output

9


Input

5 8
1 -8 20
2 -4 0
-1 10 -10
0 1 0
0 -1 1
1 9
1 4
0 10
3 11
7 9
2 1 3
1 2 3
2 3 3
3 2 3
3 4 3
4 3 3
4 5 3
5 4 3


Output

46

Note

In the first sample, f1(x) = x, f2(x) = x + 1, and f3(x) = x + 2, so we are to maximize the sum of the generating levels. The restrictions are x1 ≤ x2, x2 ≤ x3, and x3 ≤ x1, which gives us x1 = x2 = x3. The optimal configuration is x1 = x2 = x3 = 2, which produces an output of 9.

In the second sample, restrictions are equal to |xi - xi + 1| ≤ 3 for 1 ≤ i < n. One of the optimal configurations is x1 = 1, x2 = 4, x3 = 5, x4 = 8 and x5 = 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kolya loves putting gnomes at the circle table and giving them coins, and Tanya loves studying triplets of gnomes, sitting in the vertexes of an equilateral triangle.

More formally, there are 3n gnomes sitting in a circle. Each gnome can have from 1 to 3 coins. Let's number the places in the order they occur in the circle by numbers from 0 to 3n - 1, let the gnome sitting on the i-th place have a_{i} coins. If there is an integer i (0 ≤ i < n) such that a_{i} + a_{i} + n + a_{i} + 2n ≠ 6, then Tanya is satisfied. 

Count the number of ways to choose a_{i} so that Tanya is satisfied. As there can be many ways of distributing coins, print the remainder of this number modulo 10^9 + 7. Two ways, a and b, are considered distinct if there is index i (0 ≤ i < 3n), such that a_{i} ≠ b_{i} (that is, some gnome got different number of coins in these two ways).


-----Input-----

A single line contains number n (1 ≤ n ≤ 10^5) — the number of the gnomes divided by three.


-----Output-----

Print a single number — the remainder of the number of variants of distributing coins that satisfy Tanya modulo 10^9 + 7.


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

Output
20
Input
2

Output
680


-----Note-----

20 ways for n = 1 (gnome with index 0 sits on the top of the triangle, gnome 1 on the right vertex, gnome 2 on the left vertex): [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Brandon Greg Jr. considers an array to be scary if its leftmost element is the median of its elements. Given an array with distinct elements $[p_1, p_2, \ldots , p_ n]$, Brandon wants to count the number of scary subarrays.

A subarray is some contiguous chunk of elements $[p_ l, p_{l+1}, \ldots , p_ r]$ where $l\le r$. The median of a set of $n$ numbers is the middle number in sorted order if $n$ is odd, or the average of the middle two numbers in sorted order if $n$ is even. Note that all subarrays of length $1$ are scary, and no even-length subarrays are scary because the elements are all distinct.

-----Input-----
The first line of input contains a single integer $n$ ($1\le n\le 2\cdot 10^5$), representing the length of the given array.

The second line of input contains $n$ space-separated integers $p_ i$ ($1\le p_ i\le n$), representing the given array. It is guaranteed that the $p_ i$’s are distinct.

-----Output-----
Output one integer representing the number of scary subarrays.

-----Examples-----
Sample Input 1:
5
1 2 3 4 5
Sample Output 1:
5

Sample Input 2:
6
3 2 1 6 4 5
Sample Output 2:
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the probability theory the following paradox called Benford's law is known: "In many lists of random numbers taken from real sources, numbers starting with digit 1 occur much more often than numbers starting with any other digit" (that's the simplest form of the law).

Having read about it on Codeforces, the Hedgehog got intrigued by the statement and wishes to thoroughly explore it. He finds the following similar problem interesting in particular: there are N random variables, the i-th of which can take any integer value from some segment [Li;Ri] (all numbers from this segment are equiprobable). It means that the value of the i-th quantity can be equal to any integer number from a given interval [Li;Ri] with probability 1 / (Ri - Li + 1).

The Hedgehog wants to know the probability of the event that the first digits of at least K% of those values will be equal to one. In other words, let us consider some set of fixed values of these random variables and leave only the first digit (the MSD — most significant digit) of each value. Then let's count how many times the digit 1 is encountered and if it is encountered in at least K per cent of those N values, than such set of values will be called a good one. You have to find the probability that a set of values of the given random variables will be a good one.

Input

The first line contains number N which is the number of random variables (1 ≤ N ≤ 1000). Then follow N lines containing pairs of numbers Li, Ri, each of whom is a description of a random variable. It is guaranteed that 1 ≤ Li ≤ Ri ≤ 1018.

The last line contains an integer K (0 ≤ K ≤ 100).

All the numbers in the input file are integers.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Output

Print the required probability. Print the fractional number with such a precision that the relative or absolute error of the result won't exceed 10 - 9.

Examples

Input

1
1 2
50


Output

0.500000000000000

Input

2
1 2
9 11
50


Output

0.833333333333333

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.