vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
When you divide the successive powers of `10` by `13` you get the following remainders of the integer divisions:  

`1, 10, 9, 12, 3, 4`. 

Then the whole pattern repeats.

Hence the following method:
Multiply the right most digit of the number with the left most number 
in the sequence shown above, the second right most digit to the second 
left most digit of the number in the sequence. The cycle goes on and you sum all these products. Repeat this process until the sequence of sums is stationary.

...........................................................................

Example: What is the remainder when `1234567` is divided by `13`?

`7×1 + 6×10 + 5×9 + 4×12 + 3×3 + 2×4 + 1×1 = 178`

We repeat the process with 178:

`8x1 + 7x10 + 1x9 = 87`

and again with 87:

`7x1 + 8x10 = 87`

...........................................................................

From now on the sequence is stationary and the remainder of `1234567` by `13` is 
the same as the remainder of `87` by `13`: `9`

Call `thirt` the function which processes this sequence of operations on an integer `n (>=0)`. `thirt` will return the stationary number.

`thirt(1234567)` calculates 178, then 87, then 87 and returns `87`.

`thirt(321)` calculates 48, 48 and returns `48`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Those days, many boys use beautiful girls' photos as avatars in forums. So it is pretty hard to tell the gender of a user at the first glance. Last year, our hero went to a forum and had a nice chat with a beauty (he thought so). After that they talked very often and eventually they became a couple in the network. 

But yesterday, he came to see "her" in the real world and found out "she" is actually a very strong man! Our hero is very sad and he is too tired to love again now. So he came up with a way to recognize users' genders by their user names.

This is his method: if the number of distinct characters in one's user name is odd, then he is a male, otherwise she is a female. You are given the string that denotes the user name, please help our hero to determine the gender of this user by his method.


-----Input-----

The first line contains a non-empty string, that contains only lowercase English letters — the user name. This string contains at most 100 letters.


-----Output-----

If it is a female by our hero's method, print "CHAT WITH HER!" (without the quotes), otherwise, print "IGNORE HIM!" (without the quotes).


-----Examples-----
Input
wjmzbmr

Output
CHAT WITH HER!

Input
xiaodao

Output
IGNORE HIM!

Input
sevenkplus

Output
CHAT WITH HER!



-----Note-----

For the first example. There are 6 distinct characters in "wjmzbmr". These characters are: "w", "j", "m", "z", "b", "r". So wjmzbmr is a female and you should print "CHAT WITH HER!".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem, we'll use the term "longest common substring" loosely.  It refers to substrings differing at some number or fewer characters when compared index by index.  For example, 'abc' and 'adc' differ in one position, 'aab' and 'aba' differ in two.  

Given two strings and an integer $\boldsymbol{\mbox{k}}$, determine the length of the longest common substrings of the two strings that differ in no more than $\boldsymbol{\mbox{k}}$ positions.  

For example, $k=1$.  Strings $s1=abcd$ and $s2=bbca$.  Check to see if the whole string (the longest substrings) matches.  Given that neither the first nor last characters match and $2>k$, we need to try shorter substrings.  The next longest substrings are $s1'=[abc,bcd]$ and $s2'=[bbc,bca]$.  Two pairs of these substrings only differ in $\mbox{1}$ position: $[abc,bbc]$ and $[bcd,bca]$.  They are of length $3$.  

Function Description

Complete the substringDiff function in the editor below.  It should return an integer that represents the length of the longest common substring as defined.  

substringDiff has the following parameter(s):  

k: an integer that represents the maximum number of differing characters in a matching pair  
s1: the first string  
s2: the second string  

Input Format

The first line of input contains a single integer, $\boldsymbol{\boldsymbol{t}}$, the number of test cases follow. 

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains three space-separated values:  an integer $\boldsymbol{\mbox{k}}$ and two strings, $\mbox{sI}$ and $\mbox{s2}$.

Constraints

$1\leq t\leq10$  
$0\leq k\leq|s1|$   
$|s1|=|s2|$  
$1\leq|s1|,|s2|\leq1500$
All characters in $\mbox{s1}$ and $s2\in a s c i[a-z]$.

Output Format

For each test case, output a single integer which is the length of the maximum length common substrings differing at $\boldsymbol{\mbox{k}}$ or fewer positions.

Sample Input
3
2 tabriz torino
0 abacba abcaba
3 helloworld yellomarin

Sample Output
4
3
8

Explanation

First test case: If we take "briz" from the first string, and "orin" from the second string, then the number of mismatches between these two substrings is equal to 2 and their lengths are $4$.

Second test case: Since $k=0$, we should find the longest common substring, standard definition, for the given input strings. We choose "aba" as the result.

Third test case: We can choose "hellowor" from first string and "yellomar" from the second string.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pasha is a good student and one of MoJaK's best friends. He always have a problem to think about. Today they had a talk about the following problem.

We have a forest (acyclic undirected graph) with n vertices and m edges. There are q queries we should answer. In each query two vertices v and u are given. Let V be the set of vertices in the connected component of the graph that contains v, and U be the set of vertices in the connected component of the graph that contains u. Let's add an edge between some vertex <image> and some vertex in <image> and compute the value d of the resulting component. If the resulting component is a tree, the value d is the diameter of the component, and it is equal to -1 otherwise. What is the expected value of d, if we choose vertices a and b from the sets uniformly at random?

Can you help Pasha to solve this problem?

The diameter of the component is the maximum distance among some pair of vertices in the component. The distance between two vertices is the minimum number of edges on some path between the two vertices.

Note that queries don't add edges to the initial forest. 

Input

The first line contains three integers n, m and q(1 ≤ n, m, q ≤ 105) — the number of vertices, the number of edges in the graph and the number of queries.

Each of the next m lines contains two integers ui and vi (1 ≤ ui, vi ≤ n), that means there is an edge between vertices ui and vi.

It is guaranteed that the given graph is a forest.

Each of the next q lines contains two integers ui and vi (1 ≤ ui, vi ≤ n) — the vertices given in the i-th query.

Output

For each query print the expected value of d as described in the problem statement.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6. Let's assume that your answer is a, and the jury's answer is b. The checker program will consider your answer correct, if <image>.

Examples

Input

3 1 2
1 3
3 1
2 3


Output

-1
2.0000000000


Input

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


Output

-1
2.6666666667
2.6666666667

Note

In the first example the vertices 1 and 3 are in the same component, so the answer for the first query is -1. For the second query there are two options to add the edge: one option is to add the edge 1 - 2, the other one is 2 - 3. In both ways the resulting diameter is 2, so the answer is 2.

In the second example the answer for the first query is obviously -1. The answer for the second query is the average of three cases: for added edges 1 - 2 or 1 - 3 the diameter is 3, and for added edge 1 - 4 the diameter is 2. Thus, the answer is <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya is going to the Olympics in the city Ntown by train. The boy wants to read the textbook to prepare for the Olympics. He counted that he needed k hours for this. He also found that the light in the train changes every hour. The light is measured on a scale from 0 to 100, where 0 is very dark, and 100 is very light.

Vasya has a train lighting schedule for all n hours of the trip — n numbers from 0 to 100 each (the light level in the first hour, the second hour and so on). During each of those hours he will either read the whole time, or not read at all. He wants to choose k hours to read a book, not necessarily consecutive, so that the minimum level of light among the selected hours were maximum. Vasya is very excited before the upcoming contest, help him choose reading hours.


-----Input-----

The first input line contains two integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n) — the number of hours on the train and the number of hours to read, correspondingly. The second line contains n space-separated integers a_{i} (0 ≤ a_{i} ≤ 100), a_{i} is the light level at the i-th hour.


-----Output-----

In the first output line print the minimum light level Vasya will read at. In the second line print k distinct space-separated integers b_1, b_2, ..., b_{k}, — the indexes of hours Vasya will read at (1 ≤ b_{i} ≤ n). The hours are indexed starting from 1. If there are multiple optimal solutions, print any of them. Print the numbers b_{i} in an arbitrary order.


-----Examples-----
Input
5 3
20 10 30 40 10

Output
20
1 3 4 

Input
6 5
90 20 35 40 60 100

Output
35
1 3 4 5 6 



-----Note-----

In the first sample Vasya should read at the first hour (light 20), third hour (light 30) and at the fourth hour (light 40). The minimum light Vasya will have to read at is 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, the power of the string is the maximum length of a non-empty substring that contains only one unique character.
Return the power of the string.
 
Example 1:
Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.

Example 2:
Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.

Example 3:
Input: s = "triplepillooooow"
Output: 5

Example 4:
Input: s = "hooraaaaaaaaaaay"
Output: 11

Example 5:
Input: s = "tourist"
Output: 1

 
Constraints:

1 <= s.length <= 500
s contains only lowercase English letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We write the integers of A and B (in the order they are given) on two separate horizontal lines.
Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:

A[i] == B[j];
The line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.
Return the maximum number of connecting lines we can draw in this way.
 
Example 1:

Input: A = [1,4,2], B = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.


Example 2:
Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3


Example 3:
Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2
 


Note:

1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Andrey's favourite number is *n*. Andrey's friends gave him two identical numbers *n* as a New Year present. He hung them on a wall and watched them adoringly.

Then Andrey got bored from looking at the same number and he started to swap digits first in one, then in the other number, then again in the first number and so on (arbitrary number of changes could be made in each number). At some point it turned out that if we sum the resulting numbers, then the number of zeroes with which the sum will end would be maximum among the possible variants of digit permutations in those numbers.

Given number *n*, can you find the two digit permutations that have this property?

Input Specification:
The first line contains a positive integer *n* — the original number. The number of digits in this number does not exceed 105. The number is written without any leading zeroes.

Output Specification:
Print two permutations of digits of number *n*, such that the sum of these numbers ends with the maximum number of zeroes. The permutations can have leading zeroes (if they are present, they all should be printed). The permutations do not have to be different. If there are several answers, print any of them.

Demo Input:
['198\n', '500\n']

Demo Output:
['981\n819\n', '500\n500\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:


Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Red bold fonts show the difference from C1.

There is an infinitely large triangular grid, as shown below. Each point with integer coordinates contains a lamp.

<image>

Initially, only the lamp at (X, Y) was on, and all other lamps were off. Then, Snuke performed the following operation zero or more times:

* Choose two integers x and y. Toggle (on to off, off to on) the following three lamps: (x, y), (x, y+1), (x+1, y).



After the operations, N lamps (x_1, y_1), \cdots, (x_N, y_N) are on, and all other lamps are off. Find X and Y.

Constraints

* 1 \leq N \leq 10^4
* -10^{17} \leq x_i, y_i \leq 10^{17}
* (x_i, y_i) are pairwise distinct.
* The input is consistent with the statement, and you can uniquely determine X and Y.

Input

Input is given from Standard Input in the following format:


N
x_1 y_1
:
x_N y_N


Output

Print X and Y, separated by a space.

Example

Input

4
-2 1
-2 2
0 1
1 0


Output

-1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are an officer of the Department of Land and Transport in Oykot City. The department has a plan to build a subway network in the city central of Oykot.

In the plan, n subway lines are built, and each line has two or more stations. Because of technical problems, a rail track between two stations should be straight and should not have any slope. To make things worse, no rail track can contact with another rail track, even on a station. In other words, two subways on the same floor cannot have any intersection.

Your job is to calculate the least number of required floors in their plan.



Input

The input consists of multiple datasets. Each dataset is formatted as follows:


N
Line1
Line2
...
LineN


Here, N is a positive integer that indicates the number of subway lines to be built in the plan (N ≤ 22), and Linei is the description of the i-th subway line with the following format:


S
X1 Y1
X2 Y2
...
XS YS


S is a positive integer that indicates the number of stations in the line (S ≤ 30), and (Xi, Yi) indicates the coordinates of the i-th station of the line (-10000 ≤ Xi, Yi ≤ 10000). The rail tracks are going to be built between two consecutive stations in the description. No stations of the same line have the same coordinates.

The input is terminated by a dataset of N = 0, and it should not be processed.

Output

For each dataset, you should output the least number of required floors.

Example

Input

2
2
0 0
10 0
2
0 10
10 10
2
2
0 0
10 10
2
0 10
10 0
3
2
0 0
10 10
2
0 10
10 0
2
1 0
1 10
0


Output

1
2
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Allen has a LOT of money. He has $n$ dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are $1$, $5$, $10$, $20$, $100$. What is the minimum number of bills Allen could receive after withdrawing his entire balance?

Input Specification:
The first and only line of input contains a single integer $n$ ($1 \le n \le 10^9$).

Output Specification:
Output the minimum number of bills that Allen could receive.

Demo Input:
['125\n', '43\n', '1000000000\n']

Demo Output:
['3\n', '5\n', '10000000\n']

Note:
In the first sample case, Allen can withdraw this with a $100$ dollar bill, a $20$ dollar bill, and a $5$ dollar bill. There is no way for Allen to receive $125$ dollars in one or two bills.

In the second sample case, Allen can withdraw two $20$ dollar bills and three $1$ dollar bills.

In the third sample case, Allen can withdraw $100000000$ (ten million!) $100$ dollar bills.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a Binary Tree and a target key you need to find the level of target key in the given Binary Tree.
Note: The level of the root node is 1.
           3
         /   \
        2     5
      /   \
     1     4
Key: 4
Level: 3  
Note: if no such key exists then return 0.
Example 1:
Input:
        1
      /   \
     2     3
target = 4
Output: 0
Example 2:
Input:
         3
       /   \
      2     5
    /   \
   1     4
target = 4
Output: 3
Your Task:
 You don't have to take input. Just complete the function getLevel() that takes a node and a target as parameters and returns the level of the target value. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(H).
Note: H is the height of the tree and this space is used implicitly for recursion stack.
Constraints:
1 <= Number of nodes<= 10^{5}
1 <= Data of a node<= 10^{5}
1 <= Target <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a system of n water taps all pouring water into the same container. The i-th water tap can be set to deliver any amount of water from 0 to ai ml per second (this amount may be a real number). The water delivered by i-th tap has temperature ti.

If for every <image> you set i-th tap to deliver exactly xi ml of water per second, then the resulting temperature of water will be <image> (if <image>, then to avoid division by zero we state that the resulting water temperature is 0).

You have to set all the water taps in such a way that the resulting temperature is exactly T. What is the maximum amount of water you may get per second if its temperature has to be T?

Input

The first line contains two integers n and T (1 ≤ n ≤ 200000, 1 ≤ T ≤ 106) — the number of water taps and the desired temperature of water, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106) where ai is the maximum amount of water i-th tap can deliver per second.

The third line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 106) — the temperature of water each tap delivers.

Output

Print the maximum possible amount of water with temperature exactly T you can get per second (if it is impossible to obtain water with such temperature, then the answer is considered to be 0).

Your answer is considered correct if its absolute or relative error doesn't exceed 10 - 6.

Examples

Input

2 100
3 10
50 150


Output

6.000000000000000


Input

3 9
5 5 30
6 6 10


Output

40.000000000000000


Input

2 12
1 3
10 15


Output

1.666666666666667

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little X and Little Z are good friends. They always chat online. But both of them have schedules.

Little Z has fixed schedule. He always online at any moment of time between *a*1 and *b*1, between *a*2 and *b*2, ..., between *a**p* and *b**p* (all borders inclusive). But the schedule of Little X is quite strange, it depends on the time when he gets up. If he gets up at time 0, he will be online at any moment of time between *c*1 and *d*1, between *c*2 and *d*2, ..., between *c**q* and *d**q* (all borders inclusive). But if he gets up at time *t*, these segments will be shifted by *t*. They become [*c**i*<=+<=*t*,<=*d**i*<=+<=*t*] (for all *i*).

If at a moment of time, both Little X and Little Z are online simultaneosly, they can chat online happily. You know that Little X can get up at an integer moment of time between *l* and *r* (both borders inclusive). Also you know that Little X wants to get up at the moment of time, that is suitable for chatting with Little Z (they must have at least one common moment of time in schedules). How many integer moments of time from the segment [*l*,<=*r*] suit for that?

Input Specification:
The first line contains four space-separated integers *p*,<=*q*,<=*l*,<=*r* (1<=≤<=<=*p*,<=*q*<=≤<=50; 0<=≤<=*l*<=≤<=*r*<=≤<=1000).

Each of the next *p* lines contains two space-separated integers *a**i*,<=*b**i* (0<=≤<=*a**i*<=&lt;<=*b**i*<=≤<=1000). Each of the next *q* lines contains two space-separated integers *c**j*,<=*d**j* (0<=≤<=*c**j*<=&lt;<=*d**j*<=≤<=1000).

It's guaranteed that *b**i*<=&lt;<=*a**i*<=+<=1 and *d**j*<=&lt;<=*c**j*<=+<=1 for all valid *i* and *j*.

Output Specification:
Output a single integer — the number of moments of time from the segment [*l*,<=*r*] which suit for online conversation.

Demo Input:
['1 1 0 4\n2 3\n0 1\n', '2 3 0 20\n15 17\n23 26\n1 4\n7 11\n15 17\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lukas is a Civil Engineer who loves designing road networks to connect $n$ cities numbered from $1$ to $n$. He can build any number of bidirectional roads as long as the resultant network satisfies these constraints:

It must be possible to reach any city from any other city by traveling along the network of roads.  
No two roads can directly connect the same two cities.   
A road cannot directly connect a city to itself.  

In other words, the roads and cities must form a simple connected labeled graph.

You must answer $\textit{q}$ queries, where each query consists of some $n$ denoting the number of cities Lukas wants to design a bidirectional network of roads for. For each query, find and print the number of ways he can build roads connecting $n$ cities on a new line; as the number of ways can be quite large, print it modulo $663224321$.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries. 

Each of the $\textit{q}$ subsequent lines contains an integer denoting the value of $n$ for a query.

Constraints

$1\leq q,n\leq10^5$

Output Format

For each of the $\textit{q}$ queries, print the number of ways Lukas can build a network of bidirectional roads connecting $n$ cities, modulo $663224321$, on a new line.

Sample Input 0
3
1
3
10

Sample Output 0
1
4
201986643

Explanation 0

We answer the first two queries like this:

When $n=1$, the only option satisfying Lukas' three constraints is to not build any roads at all. Thus, we print the result of $1~\text{mod}~663224321=1$ on a new line.  

When $n=3$, there are four ways for Lukas to build roads that satisfy his three constraints:

Thus, we print the result of $4~\text{mod}~663224321=4$ on a new line.

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