vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Background

The kindergarten attached to the University of Aizu is a kindergarten where children who love programming gather. Yu, one of the kindergarten children, loves drawing as much as programming. So far, Yu-kun has drawn many pictures with circles and arrows. The arrows are always drawn to connect the circles. One day Yu finds out that these pictures are graphs.

It seems that circles are called vertices and arrows are called edges. Furthermore, when drawing an arrow, Yu always wrote one positive integer on it. A graph consisting of directed edges with weights in this way is called a weighted directed graph.

Today Yu-kun learned a new word, the cycle of the cycle. A cycle is a sequence of connected edges in which all vertices appear at most once, and the first and last vertices are the same. If the sum of the weights of the edges of a cycle is negative, then such a cycle is called a negative cycle.

Yu-kun, who knew a lot of new words, came up with a problem.

Problem

A weighted directed graph with no cycle is given. Select two different vertices i and j and add one directed edge with weight w (w <0) from i to j. Find i and j in the graph that create a negative cycle, and find the maximum sum of the weights of the sides that belong to that negative cycle. If such i, j does not exist, output "NA".

Constraints

The input satisfies the following conditions.

* 2 ≤ V ≤ 100000
* 1 ≤ E ≤ 500000
* -100 ≤ w <0
* 0 ≤ ci ≤ 100 (0 ≤ i ≤ E-1)
* 0 ≤ si, ti ≤ V-1 (0 ≤ i ≤ E-1)
* The same si and ti pair never appears while typing
* si and ti are different

Input


V E w
s0 t0 c0
s1 t1 c1
...
s (E-1) t (E-1) c (E-1)


The number of vertices V, the number of edges E, and the weight w of the edge to be added are given in the first line, separated by blanks.

The information of the directed edge is given as si ti ci in the following E line. (0 ≤ i ≤ E-1)

This means that there is a directed edge of the weight ci from si to ti.

Output

Output the maximum value of the sum of the weights of the sides belonging to the negative cycle, which can be created by adding the directed side of the weight w, to one line. If a negative cycle cannot be created no matter where you add an edge, output "NA".

Examples

Input

3 2 -3
0 1 1
0 2 5


Output

-2


Input

3 2 -1
0 1 1
0 2 5


Output

NA


Input

7 8 -8
0 1 5
0 4 3
1 2 10
1 3 1
3 6 6
4 3 1
4 5 2
4 6 2


Output

-1


Input

5 4 -30
0 1 1
1 3 15
1 4 4
2 1 3


Output

-12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day while playing with GCD (Greatest Common Divisor), Panda got struck in a problem, so help Panda to solve his problem. His problem follows as - Panda have N integers, for each integer count the number of subsets with gcd i%1000000007, where i denotes the ith integer which panda have.

INPUT: 
Input consists of two lines.
The first line contains the integer N.
Next line contains N integers.

OUTPUT:
N space separated integers, where each integer represents the number of subsets with gcd  i%1000000007, where i denotes the ith integer which panda have.

CONSTRAINTS:
1 ≤ N ≤ 10^6  
1 ≤ Ai ≤ N

SAMPLE INPUT
4
3 2 2 3

SAMPLE OUTPUT
3 3 3 3

Explanation

The number of subsets with the gcd of 2 is 3. They are {[2],[2],[2,2]}.  

The number of subsets with the gcd of 3 is 3. It is {[3],[3],[3,3]}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have to write a function that describe Leo:
```python
def leo(oscar):
  pass
```

if oscar was (integer) 88, you have to return "Leo finally won the oscar! Leo is happy".
if oscar was 86, you have to return "Not even for Wolf of wallstreet?!"
if it was not 88 or 86 (and below 88) you should return "When will you give Leo an Oscar?"
if it was over 88 you should return "Leo got one already!"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a collection of distinct integers, return all possible permutations.

Example:


Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have been presented with a cipher, your goal is to re-create the cipher with little information. Use the examples provided to see if you can find a solution to how this cipher is made. You will be given no hints, only the handful of phrases that have already been deciphered for you. 

Your only hint: Spaces are left alone, they are not altered in any way. Anytime there is a space, it should remain untouched and in place.

I hope you enjoy, but this one should be genuinely infuriating.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We ask you to select some number of positive integers, and calculate the sum of them.
It is allowed to select as many integers as you like, and as large integers as you wish.
You have to follow these, however: each selected integer needs to be a multiple of A, and you need to select at least one integer.
Your objective is to make the sum congruent to C modulo B.
Determine whether this is possible.
If the objective is achievable, print YES. Otherwise, print NO.

-----Constraints-----
 - 1 ≤ A ≤ 100
 - 1 ≤ B ≤ 100
 - 0 ≤ C < B

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

-----Output-----
Print YES or NO.

-----Sample Input-----
7 5 1

-----Sample Output-----
YES

For example, if you select 7 and 14, the sum 21 is congruent to 1 modulo 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The R1 company has recently bought a high rise building in the centre of Moscow for its main office. It's time to decorate the new office, and the first thing to do is to write the company's slogan above the main entrance to the building.

The slogan of the company consists of n characters, so the decorators hung a large banner, n meters wide and 1 meter high, divided into n equal squares. The first character of the slogan must be in the first square (the leftmost) of the poster, the second character must be in the second square, and so on.

Of course, the R1 programmers want to write the slogan on the poster themselves. To do this, they have a large (and a very heavy) ladder which was put exactly opposite the k-th square of the poster. To draw the i-th character of the slogan on the poster, you need to climb the ladder, standing in front of the i-th square of the poster. This action (along with climbing up and down the ladder) takes one hour for a painter. The painter is not allowed to draw characters in the adjacent squares when the ladder is in front of the i-th square because the uncomfortable position of the ladder may make the characters untidy. Besides, the programmers can move the ladder. In one hour, they can move the ladder either a meter to the right or a meter to the left.

Drawing characters and moving the ladder is very tiring, so the programmers want to finish the job in as little time as possible. Develop for them an optimal poster painting plan!


-----Input-----

The first line contains two integers, n and k (1 ≤ k ≤ n ≤ 100) — the number of characters in the slogan and the initial position of the ladder, correspondingly. The next line contains the slogan as n characters written without spaces. Each character of the slogan is either a large English letter, or digit, or one of the characters: '.', '!', ',', '?'.


-----Output-----

In t lines, print the actions the programmers need to make. In the i-th line print:  "LEFT" (without the quotes), if the i-th action was "move the ladder to the left";  "RIGHT" (without the quotes), if the i-th action was "move the ladder to the right";  "PRINT x" (without the quotes), if the i-th action was to "go up the ladder, paint character x, go down the ladder". 

The painting time (variable t) must be minimum possible. If there are multiple optimal painting plans, you can print any of them.


-----Examples-----
Input
2 2
R1

Output
PRINT 1
LEFT
PRINT R

Input
2 1
R1

Output
PRINT R
RIGHT
PRINT 1

Input
6 4
GO?GO!

Output
RIGHT
RIGHT
PRINT !
LEFT
PRINT O
LEFT
PRINT G
LEFT
PRINT ?
LEFT
PRINT O
LEFT
PRINT G



-----Note-----

Note that the ladder cannot be shifted by less than one meter. The ladder can only stand in front of some square of the poster. For example, you cannot shift a ladder by half a meter and position it between two squares. Then go up and paint the first character and the second character.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the United States of America, telephone numbers within an area code consist of seven digits: the prefix number is the first three digits and the line number is the last four digits. Traditionally, the $555$ prefix number has been used to provide directory information and assistance as in the following examples:
 - 555-1212
 - 555-9876
 - 555-5000
 - 555-7777

Telephone company switching hardware would detect the $555$ prefix and route the call to a directory information operator. Nowadays, telephone switching is done digitally and somewhere along the line a computer decides where to route calls.

For this problem, write a program that determines if a supplied seven-digit telephone number should be routed to the directory information operator, that is, the prefix number is $555$.

-----Input-----
The single line of input contains a single integer $n$ ($1000000 \le n \le 9999999$), which is a telephone number.

-----Output-----
Output a single integer, which is $1$ if the number should be routed to the directory information operator, or $0$ if the number should not be routed to the directory information operator.

-----Examples-----
Sample Input 1:
5551212
Sample Output 1:
1

Sample Input 2:
5519876
Sample Output 2:
0

Sample Input 3:
5055555
Sample Output 3:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice has a positive integer N. She is wondering how many ordered pairs of positive integers (i, j) exist such that i + j = N. 

Help Alice figure out the answer.

Note that since the pairs are ordered, (1, 2) and (2, 1) are considered different.

------ Input Format ------ 

The first and only line of input contains a single integer N.

------ Output Format ------ 

Print a single integer, the number of ordered pairs of positive integers (i, j) such that i + j = N.

------ Constraints ------ 

$1 ≤ N ≤ 100$

----- Sample Input 1 ------ 
1
----- Sample Output 1 ------ 
0
----- explanation 1 ------ 
As both integers must be positive, the minimum sum must be $1 + 1 = 2$. Therefore there are no pairs of positive integers adding up to $1$.

----- Sample Input 2 ------ 
2
----- Sample Output 2 ------ 
1
----- explanation 2 ------ 
$(1,1)$ is the only pair whose sum is $2$. Every other pair has a sum of at least $3$.

----- Sample Input 3 ------ 
3
----- Sample Output 3 ------ 
2
----- explanation 3 ------ 
The two pairs are $(1, 2)$ and $(2, 1)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gosha is hunting. His goal is to catch as many Pokemons as possible. Gosha has a Poke Balls and b Ultra Balls. There are n Pokemons. They are numbered 1 through n. Gosha knows that if he throws a Poke Ball at the i-th Pokemon he catches it with probability pi. If he throws an Ultra Ball at the i-th Pokemon he catches it with probability ui. He can throw at most one Ball of each type at any Pokemon.

The hunting proceeds as follows: at first, Gosha chooses no more than a Pokemons at which he will throw Poke Balls and no more than b Pokemons at which he will throw Ultra Balls. After that, he throws the chosen Balls at the chosen Pokemons. If he throws both Ultra Ball and Poke Ball at some Pokemon, he is caught if and only if he is caught by any of these Balls. The outcome of a throw doesn't depend on the other throws.

Gosha would like to know what is the expected number of the Pokemons he catches if he acts in an optimal way. In other words, he would like to know the maximum possible expected number of Pokemons can catch.

Input

The first line contains three integers n, a and b (2 ≤ n ≤ 2000, 0 ≤ a, b ≤ n) — the number of Pokemons, the number of Poke Balls and the number of Ultra Balls.

The second line contains n real values p1, p2, ..., pn (0 ≤ pi ≤ 1), where pi is the probability of catching the i-th Pokemon if Gosha throws a Poke Ball to it.

The third line contains n real values u1, u2, ..., un (0 ≤ ui ≤ 1), where ui is the probability of catching the i-th Pokemon if Gosha throws an Ultra Ball to it.

All the probabilities are given with exactly three digits after the decimal separator.

Output

Print the maximum possible expected number of Pokemons Gosha can catch. The answer is considered correct if it's absolute or relative error doesn't exceed 10 - 4.

Examples

Input

3 2 2
1.000 0.000 0.500
0.000 1.000 0.500


Output

2.75


Input

4 1 3
0.100 0.500 0.500 0.600
0.100 0.500 0.900 0.400


Output

2.16


Input

3 2 0
0.412 0.198 0.599
0.612 0.987 0.443


Output

1.011

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given the centers of three equal sides of a strictly convex tetragon. Your task is to restore the initial tetragon.

Input

The first input line contains one number T — amount of tests (1 ≤ T ≤ 5·104). Each of the following T lines contains numbers x1, y1, x2, y2, x3, y3 — coordinates of different points that are the centers of three equal sides (non-negative integer numbers, not exceeding 10).

Output

For each test output two lines. If the required tetragon exists, output in the first line YES, in the second line — four pairs of numbers — coordinates of the polygon's vertices in clockwise or counter-clockwise order. Don't forget, please, that the tetragon should be strictly convex, i.e. no 3 of its points lie on one line. Output numbers with 9 characters after a decimal point.

If the required tetragon doen't exist, output NO in the first line, and leave the second line empty.

Examples

Input

3
1 1 2 2 3 3
0 1 1 0 2 2
9 3 7 9 9 8


Output

NO

YES
3.5 1.5 0.5 2.5 -0.5 -0.5 2.5 0.5
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements [Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Chef is a cook and he has recently opened a restaurant.

The restaurant is open during $N$ time intervals $[L_{1}, R_{1}), [L_{2}, R_{2}), \dots, [L_{N}, R_{N})$. No two of these intervals overlap — formally, for each valid $i$, $j$ such that $i \neq j$, either $R_{i} < L_{j}$ or $R_{j} < L_{i}$.

$M$ people (numbered $1$ through $M$) are planning to eat at the restaurant; let's denote the time when the $i$-th person arrives by $P_{i}$. If the restaurant is open at that time, this person does not have to wait, but if it is closed, this person will wait until it is open. Note that if this person arrives at an exact time when the restaurant is closing, they have to wait for the next opening time.

For each person, calculate how long they have to wait (possibly $0$ time), or determine that they will wait forever for the restaurant to open.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of the input contains two space-separated integers $N$ and $M$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $L_{i}$ and $R_{i}$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains a single integer $P_{i}$.

------  Output ------
For each test case, print $M$ lines. For each valid $i$, the $i$-th of these lines should contain a single integer — the time person $i$ has to wait, or $-1$ if person $i$ has to wait forever.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 10^{5}$
$1 ≤ L_{i} < R_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ P_{i} ≤ 10^{9}$ for each valid $i$
the intervals are pairwise disjoint
the sum of $N$ for all test cases does not exceed $3 \cdot 10^{5}$
the sum of $M$ for all test cases does not exceed $3 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (30 points):
the sum of $N$ for all test cases does not exceed $1,000$
the sum of $M$ for all test cases does not exceed $1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1
4 5
5 7
9 10
2 3
20 30
5
6
7
35
1
----- Sample Output 1 ------ 
0
0
2
-1
1
----- explanation 1 ------ 
Query $1$: The person coming at time $5$ does not have to wait as the restaurant is open in $[5,7)$ slot.

Query $2$: The person coming at time $6$ does not have to wait as the restaurant is open in $[5,7)$ slot.

Query $3$: The person coming at time $7$ has to wait since the restaurant is closed at time $7$. The next slot in which the restaurant opens is $[9,10)$. Thus, the person waits for $2$ units of time.

Query $4$: The person coming at time $35$ has to wait forever as the restaurant does not open after time $30$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ points on the plane, $(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$.

You need to place an isosceles triangle with two sides on the coordinate axis to cover all points (a point is covered if it lies inside the triangle or on the side of the triangle). Calculate the minimum length of the shorter side of the triangle.


-----Input-----

First line contains one integer $n$ ($1 \leq n \leq 10^5$).

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i,y_i \leq 10^9$).


-----Output-----

Print the minimum length of the shorter side of the triangle. It can be proved that it's always an integer.


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

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

Output
4


-----Note-----

Illustration for the first example: [Image]

Illustration for the second example: [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mike and Joe are fratboys that love beer and games that involve drinking. They play the following game: Mike chugs one beer, then Joe chugs 2 beers, then Mike chugs 3 beers, then Joe chugs 4 beers, and so on. Once someone can't drink what he is supposed to drink, he loses.

Mike can chug at most A beers in total (otherwise he would pass out), while Joe can chug at most B beers in total. Who will win the game? 

Write the function ```game(A,B)``` that returns the winner, ```"Mike"``` or ```"Joe"``` accordingly, for any given integer values of A and B.

Note: If either Mike or Joe cannot drink at least 1 beer, return the string  ```"Non-drinkers can't play"```.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i-th row from the top and the j-th column from the left.
Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it.
Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.
Q queries are given. We ask you to process them in order.
There are two kinds of queries. Their input format and description are as follows:
 - 1 x: Place a white stone on (1, x). After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x), replace it with a white stone.
 - 2 x: Place a white stone on (x, 1). After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1), replace it with a white stone.
How many black stones are there on the grid after processing all Q queries?

-----Constraints-----
 - 3 \leq N \leq 2\times 10^5
 - 0 \leq Q \leq \min(2N-4,2\times 10^5)
 - 2 \leq x \leq N-1
 - Queries are pairwise distinct.

-----Input-----
Input is given from Standard Input in the following format:
N Q
Query_1
\vdots
Query_Q

-----Output-----
Print how many black stones there are on the grid after processing all Q queries.

-----Sample Input-----
5 5
1 3
2 3
1 4
2 2
1 2

-----Sample Output-----
1

After each query, the grid changes in the following way:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
A newly opened multinational brand has decided to base their company logo on the three most common characters in the company name. They are now trying out various combinations of company names and logos based on this condition. Given a string s, which is the company name in lowercase letters, your task is to find the top three most common characters in the string.
Print the three most common characters along with their occurrence count.
Sort in descending order of occurrence count.
If the occurrence count is the same, sort the characters in alphabetical order.

For example, according to the conditions described above, GOOGLE would have it's logo with the letters G, O, E. 

=====Input Format=====
A single line of input containing the string S.

=====Constraints=====
3≤len(S)≤10^4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a directed acyclic graph (a directed graph that does not contain cycles) of n vertices and m arcs. The i-th arc leads from the vertex x_i to the vertex y_i and has the weight w_i.

Your task is to select an integer a_v for each vertex v, and then write a number b_i on each arcs i such that b_i = a_{x_i} - a_{y_i}. You must select the numbers so that:

  * all b_i are positive; 
  * the value of the expression ∑ _{i = 1}^{m} w_i b_i is the lowest possible. 



It can be shown that for any directed acyclic graph with non-negative w_i, such a way to choose numbers exists.

Input

The first line contains two integers n and m (2 ≤ n ≤ 18; 0 ≤ m ≤ (n(n - 1))/(2)).

Then m lines follow, the i-th of them contains three integers x_i, y_i and w_i (1 ≤ x_i, y_i ≤ n, 1 ≤ w_i ≤ 10^5, x_i ≠ y_i) — the description of the i-th arc.

It is guaranteed that the lines describe m arcs of a directed acyclic graph without multiple arcs between the same pair of vertices.

Output

Print n integers a_1, a_2, ..., a_n (0 ≤ a_v ≤ 10^9), which must be written on the vertices so that all b_i are positive, and the value of the expression ∑ _{i = 1}^{m} w_i b_i is the lowest possible. If there are several answers, print any of them. It can be shown that the answer always exists, and at least one of the optimal answers satisfies the constraints 0 ≤ a_v ≤ 10^9.

Examples

Input


3 2
2 1 4
1 3 2


Output


1 2 0


Input


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


Output


43 42 41 1337 1336


Input


5 5
1 2 1
2 3 1
3 4 1
1 5 1
5 4 10


Output


4 3 2 1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja has an array a, consisting of n integers a_1, a_2, ..., a_{n}. The boy cannot sit and do nothing, he decided to study an array. Sereja took a piece of paper and wrote out m integers l_1, l_2, ..., l_{m} (1 ≤ l_{i} ≤ n). For each number l_{i} he wants to know how many distinct numbers are staying on the positions l_{i}, l_{i} + 1, ..., n. Formally, he want to find the number of distinct numbers among a_{l}_{i}, a_{l}_{i} + 1, ..., a_{n}.?

Sereja wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each l_{i}.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5) — the array elements.

Next m lines contain integers l_1, l_2, ..., l_{m}. The i-th line contains integer l_{i} (1 ≤ l_{i} ≤ n).


-----Output-----

Print m lines — on the i-th line print the answer to the number l_{i}.


-----Examples-----
Input
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10

Output
6
6
6
6
6
5
4
3
2
1

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