vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given two integers $A$ and $B$, $A$ modulo $B$ is the remainder when dividing $A$ by $B$. For example, the numbers $7$, $14$, $27$ and $38$ become $1$, $2$, $0$ and $2$, modulo $3$. Write a program that accepts $10$ numbers as input and outputs the number of distinct numbers in the input, if the numbers are considered modulo $42$.

-----Input-----
The input will contain 10 non-negative integers, each smaller than $1000$, one per line.

-----Output-----
Output the number of distinct values when considered modulo $42$ on a single line.

-----Explanation of Sample Inputs-----
In sample input $1$, the numbers modulo $42$ are $1, 2, 3, 4, 5, 6, 7, 8, 9$ and $10$.

In sample input $2$, all numbers modulo $42$ are $0$.

In sample input $3$, the numbers modulo $42$ are $39, 40, 41, 0, 1, 2, 40, 41, 0$ and $1$. There are $6$ distinct numbers.

-----Examples-----
Sample Input 1:
1
2
3
4
5
6
7
8
9
10
Sample Output 1:
10

Sample Input 2:
42
84
252
420
840
126
42
84
420
126
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s. You need to reverse the string.
Example 1:
Input:
s = Geeks
Output: skeeG
Example 2:
Input:
s = for
Output: rof
Your Task:
You only need to complete the function reverseWord() that takes s as parameter and returns the reversed string.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 <= |s| <= 10000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a tree with N vertices. The vertices are numbered 1, 2, ..., N. The i-th (1 ≦ i ≦ N - 1) edge connects the two vertices A_i and B_i.

Takahashi wrote integers into K of the vertices. Specifically, for each 1 ≦ j ≦ K, he wrote the integer P_j into vertex V_j. The remaining vertices are left empty. After that, he got tired and fell asleep.

Then, Aoki appeared. He is trying to surprise Takahashi by writing integers into all empty vertices so that the following condition is satisfied:

* Condition: For any two vertices directly connected by an edge, the integers written into these vertices differ by exactly 1.



Determine if it is possible to write integers into all empty vertices so that the condition is satisfied. If the answer is positive, find one specific way to satisfy the condition.

Constraints

* 1 ≦ N ≦ 10^5
* 1 ≦ K ≦ N
* 1 ≦ A_i, B_i ≦ N (1 ≦ i ≦ N - 1)
* 1 ≦ V_j ≦ N (1 ≦ j ≦ K) (21:18, a mistake in this constraint was corrected)
* 0 ≦ P_j ≦ 10^5 (1 ≦ j ≦ K)
* The given graph is a tree.
* All v_j are distinct.

Input

The input is given from Standard Input in the following format:


N
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
K
V_1 P_1
V_2 P_2
:
V_K P_K


Output

If it is possible to write integers into all empty vertices so that the condition is satisfied, print `Yes`. Otherwise, print `No`.

If it is possible to satisfy the condition, print N lines in addition. The v-th (1 ≦ v ≦ N) of these N lines should contain the integer that should be written into vertex v. If there are multiple ways to satisfy the condition, any of those is accepted.

Examples

Input

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


Output

Yes
5
6
6
5
7


Input

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


Output

No


Input

4
1 2
2 3
3 4
1
1 0


Output

Yes
0
-1
-2
-3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given N points in the xy-plane. You have a circle of radius one and move it on the xy-plane, so as to enclose as many of the points as possible. Find how many points can be simultaneously enclosed at the maximum. A point is considered enclosed by a circle when it is inside or on the circle.

<image>

Fig 1. Circle and Points



Input

The input consists of a series of data sets, followed by a single line only containing a single character '0', which indicates the end of the input. Each data set begins with a line containing an integer N, which indicates the number of points in the data set. It is followed by N lines describing the coordinates of the points. Each of the N lines has two decimal fractions X and Y, describing the x- and y-coordinates of a point, respectively. They are given with five digits after the decimal point.

You may assume 1 <= N <= 300, 0.0 <= X <= 10.0, and 0.0 <= Y <= 10.0. No two points are closer than 0.0001. No two points in a data set are approximately at a distance of 2.0. More precisely, for any two points in a data set, the distance d between the two never satisfies 1.9999 <= d <= 2.0001. Finally, no three points in a data set are simultaneously very close to a single circle of radius one. More precisely, let P1, P2, and P3 be any three points in a data set, and d1, d2, and d3 the distances from an arbitrarily selected point in the xy-plane to each of them respectively. Then it never simultaneously holds that 0.9999 <= di <= 1.0001 (i = 1, 2, 3).

Output

For each data set, print a single line containing the maximum number of points in the data set that can be simultaneously enclosed by a circle of radius one. No other characters including leading and trailing spaces should be printed.

Example

Input

3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378
6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
20
6.65128 5.47490
6.42743 6.26189
6.35864 4.61611
6.59020 4.54228
4.43967 5.70059
4.38226 5.70536
5.50755 6.18163
7.41971 6.13668
6.71936 3.04496
5.61832 4.23857
5.99424 4.29328
5.60961 4.32998
6.82242 5.79683
5.44693 3.82724
6.70906 3.65736
7.89087 5.68000
6.23300 4.59530
5.92401 4.92329
6.24168 3.81389
6.22671 3.62210
0


Output

2
5
5
11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are provided with the marks of entire class in Data structures exam out of 100. You need to calculate the number of students having backlog (passing marks is >=31) and the average of the class. But this average is not a normal average, for this average marks of students having backlog are not considered but they will be considered in number of students. Also print the index of topper’s marks and print the difference of everyone’s marks with respect to the topper. 
In first line print the number of students having backlog and average of the class. In second line print indices of all the toppers(in case of more than 1 topper print index of all toppers in reverse order). Next N lines print the difference of everyone’s marks with respect to topper(s).
Note- if all students have backlog than average will be 0.
INPUT
The first line of the input contains an integer T denoting the number of test cases.
Next line contains N denoting the no of students in the class.
The line contains N space seprated integers A1,A2,A3….AN denoting the marks of each student in exam.
OUTPUT
First line contains the number of students having backlog and the special average of marks as described above. Average must have 2 decimal places.
Next line contains the indices of all the toppers in given array in reverse order.
Next N lines contain the difference of every student’s marks with respect to toppers.
Constraints
1<= T <= 100
1<= N <= 30
0<= Ai<= 100
Example
Input
1
9
56 42 94 25 74 99 27 52 83
Output
2 55.55
5 
43
57
5
74
25
0
72
47
16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Scientist Frank, majoring in electrochemistry, has developed line-shaped strange electrodes called F-electrodes. During being activated, each F-electrode causes a special potential on and between the two lines touching the F-electrode’s endpoints at a right angle. Then electrically-charged particles located inside the potential area get to move in the direction parallel to the potential boundary (i.e. perpendicular to the F-electrode), either toward or against F-electrode. The moving direction can be easily controlled between the two possibles; it is also possible to get particles to pass through F-electrodes. In addition, unlike ordinary electrodes, F-electrodes can affect particles even infinitely far away, as long as those particles are located inside the potential area. On the other hand, two different F-electrodes cannot be activated at a time, since their potentials conflict strongly.

We can move particles on our will by controlling F-electrodes. However, in some cases, we cannot lead them to the desired positions due to the potential areas being limited. To evaluate usefulness of F-electrodes from some aspect, Frank has asked you the following task: to write a program that finds the shortest distances from the particles’ initial positions to their destinations with the given sets of F-electrodes.

<image>



Input

The input consists of multiple test cases. The first line of each case contains N (1 ≤ N ≤ 100) which represents the number of F-electrodes. The second line contains four integers xs, ys, xt and yt, where (xs, ys) and (xt, yt) indicate the particle’s initial position and destination. Then the description of N F-electrodes follow. Each line contains four integers Fxs, Fys, Fxt and Fyt, where (Fxs, Fys) and (Fxt, Fyt ) indicate the two endpoints of an F-electrode. All coordinate values range from 0 to 100 inclusive.

The input is terminated by a case with N = 0.

Output

Your program must output the case number followed by the shortest distance between the initial position to the destination. Output “Impossible” (without quotes) as the distance if it is impossible to lead the elementary particle to the destination. Your answers must be printed with five digits after the decimal point. No absolute error in your answers may exceed 10-5.

Example

Input

2
2 1 2 2
0 0 1 0
0 1 0 2
0


Output

Case 1: 3.00000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
BubbleSquare social network is celebrating 13^{th} anniversary and it is rewarding its members with special edition BubbleSquare tokens. Every member receives one personal token. Also, two additional tokens are awarded to each member for every friend they have on the network. Yet, there is a twist – everyone should end up with different number of tokens from all their friends. Each member may return one received token. Also, each two friends may agree to each return one or two tokens they have obtained on behalf of their friendship.

Input

First line of input contains two integer numbers n and k (2 ≤ n ≤ 12500, 1 ≤ k ≤ 1000000) - number of members in network and number of friendships.

Next k lines contain two integer numbers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) - meaning members a_i and b_i are friends.

Output

First line of output should specify the number of members who are keeping their personal token.

The second line should contain space separated list of members who are keeping their personal token.

Each of the following k lines should contain three space separated numbers, representing friend pairs and number of tokens each of them gets on behalf of their friendship.

Examples

Input


2 1
1 2


Output


1
1 
1 2 0


Input


3 3
1 2
1 3
2 3


Output


0
1 2 0
2 3 1
1 3 2

Note

In the first test case, only the first member will keep its personal token and no tokens will be awarded for friendship between the first and the second member.

In the second test case, none of the members will keep their personal token. The first member will receive two tokens (for friendship with the third member), the second member will receive one token (for friendship with the third member) and the third member will receive three tokens (for friendships with the first and the second member).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.
When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).
In how many ways can the knight reach the square (X, Y)?
Find the number of ways modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq X \leq 10^6
 - 1 \leq Y \leq 10^6
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
X Y

-----Output-----
Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

-----Sample Input-----
3 3

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

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given K sorted linked lists of different sizes. The task is to merge them in such a way that after merging they will be a single sorted linked list. 
Example 1:
Input:
K = 4
value = {{1,2,3},{4 5},{5 6},{7,8}}
Output: 1 2 3 4 5 5 6 7 8
Explanation:
The test case has 4 sorted linked 
list of size 3, 2, 2, 2
1st    list     1 -> 2-> 3
2nd   list      4->5
3rd    list      5->6
4th    list      7->8
The merged list will be
1->2->3->4->5->5->6->7->8.
Example 2:
Input:
K = 3
value = {{1,3},{4,5,6},{8}}
Output: 1 3 4 5 6 8
Explanation:
The test case has 3 sorted linked
list of size 2, 3, 1.
1st list 1 -> 3
2nd list 4 -> 5 -> 6
3rd list 8
The merged list will be
1->3->4->5->6->8.
Your Task:
The task is to complete the function mergeKList() which merges the K given lists into a sorted one. The printing is done automatically by the driver code.
Expected Time Complexity: O(nk Logk)
Expected Auxiliary Space: O(k)
Note: n is the maximum size of all the k link list
Constraints
1 <= K <= 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lazy caterer sequence is defined as the maximum number of pieces formed when slicing a convex pancake with n cuts (each cut is a straight line). The formula is Cn = n·(n + 1) / 2 + 1. You are given n; calculate n-th element of the sequence.

Input

The only line of the input contains an integer n (0 ≤ n ≤ 100).

Output

Output the n-th element of lazy caterer sequence.

Examples

Input

2


Output

4


Input

5


Output

16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You might have heard about the next game in Lara Croft series coming out this year. You also might have watched its trailer. Though you definitely missed the main idea about its plot, so let me lift the veil of secrecy.

Lara is going to explore yet another dangerous dungeon. Game designers decided to use good old 2D environment. The dungeon can be represented as a rectangle matrix of n rows and m columns. Cell (x, y) is the cell in the x-th row in the y-th column. Lara can move between the neighbouring by side cells in all four directions.

Moreover, she has even chosen the path for herself to avoid all the traps. She enters the dungeon in cell (1, 1), that is top left corner of the matrix. Then she goes down all the way to cell (n, 1) — the bottom left corner. Then she starts moving in the snake fashion — all the way to the right, one cell up, then to the left to the cell in 2-nd column, one cell up. She moves until she runs out of non-visited cells. n and m given are such that she always end up in cell (1, 2).

Lara has already moved to a neighbouring cell k times. Can you determine her current position?


-----Input-----

The only line contains three integers n, m and k (2 ≤ n, m ≤ 10^9, n is always even, 0 ≤ k < n·m). Note that k doesn't fit into 32-bit integer type!


-----Output-----

Print the cell (the row and the column where the cell is situated) where Lara ends up after she moves k times.


-----Examples-----
Input
4 3 0

Output
1 1

Input
4 3 11

Output
1 2

Input
4 3 7

Output
3 2



-----Note-----

Here is her path on matrix 4 by 3: [Image]

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a string *s* consisting of *n* lowercase Latin letters. Some indices in this string are marked as forbidden.

You want to find a string *a* such that the value of |*a*|·*f*(*a*) is maximum possible, where *f*(*a*) is the number of occurences of *a* in *s* such that these occurences end in non-forbidden indices. So, for example, if *s* is aaaa, *a* is aa and index 3 is forbidden, then *f*(*a*)<==<=2 because there are three occurences of *a* in *s* (starting in indices 1, 2 and 3), but one of them (starting in index 2) ends in a forbidden index.

Calculate the maximum possible value of |*a*|·*f*(*a*) you can get.

Input Specification:
The first line contains an integer number *n* (1<=≤<=*n*<=≤<=200000) — the length of *s*.

The second line contains a string *s*, consisting of *n* lowercase Latin letters.

The third line contains a string *t*, consisting of *n* characters 0 and 1. If *i*-th character in *t* is 1, then *i* is a forbidden index (otherwise *i* is not forbidden).

Output Specification:
Print the maximum possible value of |*a*|·*f*(*a*).

Demo Input:
['5\nababa\n00100\n', '5\nababa\n00000\n', '5\nababa\n11111\n']

Demo Output:
['5\n', '6\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Poornima is celebrating its annual Techno-Cultural Fest AAROHAN. The IT student Kriti has agreed to supply candies for this festive season.

Kriti has prepared N boxes of candies, numbered 1 to N (Each number occurring exactly once ). Kriti is very particular about the arrangement of boxes. She wants boxes to be arranged in a particular order, but unfortunately Kriti is busy. She has asked you to rearrange the boxes for him.

Given the current order of boxes, you have to rearrange the boxes in the specified order. However there is a restriction.You can only swap two adjacent boxes to achieve the required order. Output, the minimum number of such adjacent swaps required.

Input

First line of input contains a single integer T, number of test cases. Each test case contains 3 lines, first line contains a single integer N, number of boxes. Next 2 lines contains N numbers each, first row is the given order of boxes while second row is the required order.

Output

For each test case, output a single integer 'K', minimum number of adjacent swaps required. 

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5

SAMPLE INPUT
1

3
1 2 3
3 1 2

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
HQ9+ is a joke programming language which has only four one-character instructions:

  * "H" prints "Hello, World!",
  * "Q" prints the whole source code of the program itself (at each call),
  * "9" prints the lyrics of "99 Bottles of Beer" song, 
  * "+" increments the value stored in the internal accumulator.



Instructions "H" and "Q" are case-sensitive and must be uppercase. The characters of the program which are not instructions are ignored.

You are given a program written in HQ9+. You have to figure out whether executing this program will produce any output.

Input

The input will consist of a single line p which will give a program in HQ9+. String p will contain between 1 and 100 characters, inclusive. ASCII-code of each character of p will be between 33 (exclamation mark) and 126 (tilde), inclusive.

Output

Output "YES", if executing the program will produce any output, and "NO" otherwise (quotes for clarity only).

Examples

Input

Hello!


Output

YES


Input

Progopedia


Output

NO

Note

In the first case the program contains only one instruction — "H", which prints "Hello, World!".

In the second case none of the program characters are language instructions.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an unweighted tree with *n* vertices. Then *n*<=-<=1 following operations are applied to the tree. A single operation consists of the following steps: 
 1.  choose two leaves; 1.  add the length of the simple path between them to the answer; 1.  remove one of the chosen leaves from the tree. 
Initial answer (before applying operations) is 0. Obviously after *n*<=-<=1 such operations the tree will consist of a single vertex. 

Calculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!

Input Specification:
The first line contains one integer number *n* (2<=≤<=*n*<=≤<=2·105) — the number of vertices in the tree. 

Next *n*<=-<=1 lines describe the edges of the tree in form *a**i*,<=*b**i* (1<=≤<=*a**i*, *b**i*<=≤<=*n*, *a**i*<=≠<=*b**i*). It is guaranteed that given graph is a tree.

Output Specification:
In the first line print one integer number — maximal possible answer. 

In the next *n*<=-<=1 lines print the operations in order of their applying in format *a**i*,<=*b**i*,<=*c**i*, where *a**i*,<=*b**i* — pair of the leaves that are chosen in the current operation (1<=≤<=*a**i*, *b**i*<=≤<=*n*), *c**i* (1<=≤<=*c**i*<=≤<=*n*, *c**i*<==<=*a**i* or *c**i*<==<=*b**i*) — choosen leaf that is removed from the tree in the current operation. 

See the examples for better understanding.

Demo Input:
['3\n1 2\n1 3\n', '5\n1 2\n1 3\n2 4\n2 5\n']

Demo Output:
['3\n2 3 3\n2 1 1\n', '9\n3 5 5\n4 3 3\n4 1 1\n4 2 2\n']

Note:
none

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