vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Permutation p is an ordered set of integers p_1,  p_2,  ...,  p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. We'll denote the i-th element of permutation p as p_{i}. We'll call number n the size or the length of permutation p_1,  p_2,  ...,  p_{n}.

You have a sequence of integers a_1, a_2, ..., a_{n}. In one move, you are allowed to decrease or increase any number by one. Count the minimum number of moves, needed to build a permutation from this sequence.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5) — the size of the sought permutation. The second line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a single number — the minimum number of moves.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
2
3 0

Output
2

Input
3
-1 -1 2

Output
6



-----Note-----

In the first sample you should decrease the first number by one and then increase the second number by one. The resulting permutation is (2, 1).

In the second sample you need 6 moves to build permutation (1, 3, 2).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During one of the space missions, humans have found an evidence of previous life at one of the planets. They were lucky enough to find a book with birth and death years of each individual that had been living at this planet. What's interesting is that these years are in the range $(1, 10^9)$! Therefore, the planet was named Longlifer.

In order to learn more about Longlifer's previous population, scientists need to determine the year with maximum number of individuals that were alive, as well as the number of alive individuals in that year. Your task is to help scientists solve this problem!


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^5$) — the number of people.

Each of the following $n$ lines contain two integers $b$ and $d$ ($1 \le b \lt d \le 10^9$) representing birth and death year (respectively) of each individual.


-----Output-----

Print two integer numbers separated by blank character, $y$  — the year with a maximum number of people alive and $k$  — the number of people alive in year $y$.

In the case of multiple possible solutions, print the solution with minimum year.


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

Output
2 2

Input
4
3 4
4 5
4 6
8 10

Output
4 2



-----Note-----

You can assume that an individual living from $b$ to $d$ has been born at the beginning of $b$ and died at the beginning of $d$, and therefore living for $d$ - $b$ years.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary string S. The task is to count the number of substrings that starts and end with 1.
Note: The starting and the ending 1s should be different.
Example 1:
Input:
S = "10101"
Output: 3
Explanation: The 3 substrings are "101",
"10101" and "101".
Ã¢â¬â¹Example 2:
Input: 
S = "100"
Output: 0
Explanation: No substring that starts and
ends with 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countSubstr() which takes the string S as input and returns the count of the substrings that start and end with 1.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 <= |S| <= 1000

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

Mr. A and Mr. B are enthusiastic about the game "Changing Grids". This game is for two players, with player 1 forming the stage and player 2 challenging the stage and aiming for the goal.

Now, A and B have played this game several times, but B has never won because of A's winning streak. So you decided to give B some tips on how to capture this game.

Problem

The state of the two-dimensional grid with the size of vertical H × horizontal W at time T0 = 0 is given as Area 0. Next, the state of this grid switches to the state Areai at time Ti. This switching process is repeated N times. The initial grid is given a start position'S'and a goal position'G'. If you can reach the goal on any grid, output the minimum number of steps at that time, and if you cannot reach the goal, output'-1'. The following conditions must also be met.


* Areai consists of the following elements.
* ‘.’ Is a movable mass without anything
* ‘#’ Is an obstacle and cannot be moved.
*'S' is the square that represents the start position
*'G' is a square that represents the goal position
* It takes 1 second for the player to move to or stay in the current square, either up, down, left, or right adjacent to the current square. However, it cannot move outside the range of obstacle squares or grids.
* The number of steps increases by 1 when you move 1 square from the square where the player is currently to the squares up, down, left, and right. It does not increase if you stay on the spot.
* The size of all grids is vertical H x horizontal W.
* 1 When the grid is switched after moving or staying in place, it is possible to move regardless of the current grid state as long as there are no obstacles in the next grid.
* In all grids, if the goal position given to the initial grid is reached, it is considered as a goal.

Constraints

The input satisfies the following conditions.

* 2 ≤ H, W ≤ 20
* 1 ≤ N ≤ 15
* 1 ≤ Ti ≤ 200 (T1 <T2 <... <TN)
* There is only one start position'S'and one goal position'G' in the initial 2D grid.

Input

The input is given in the following format.


H W
Area0
N
T1
Area1
T2
Area2
..
..
TN
AreaN


Two integers H and W are given on the first line, separated by blanks. This represents the vertical and horizontal dimensions of the two-dimensional grid, respectively. The initial state of the two-dimensional grid is given to each line from the second line to the H + 1 line. The integer N is given on the second line of H +. This represents the number of changes in the 2D grid. The time Ti and the state of switching of N 2D grids are given after the 3rd line of H +. However, Ti is all integers.

Output

Output the minimum number of steps to reach the goal from the start. However, if you cannot reach the goal, output'-1'.

Examples

Input

2 2
S.
.G
1
3
##
##


Output

2


Input

2 2
S.
.G
1
3


Output

2


Input

2 2
S.
.G
1
2


Output

-1


Input

2 3
S##
G
4
2

.##
3

.#
5

.
7


Output

3


Input

4 3
S..
...
.G.
...
4
2

.#

.#
4

..
..

6

.#

..
8

..
..


Output

3


Input

3 3
S##

G
1
1
...
...
...


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The prudent Mr. Day and adventurous Dr. Knight have decided to be backpack buddies and go trekking in the gorgeous Norwegian mountains. Of course they will use the trails marked by the Norwegian Trekking Association (DNT), like any sane trekkers would; such trails all start and end at some cabin where it is possible to lay over. Mr. Day for one likes sleeping comfortably, so he immediately suggested that they sleep in a cabin every night.

However, Dr. Knight was of a different opinion; she argued that they’d arrive at their destination much quicker if they went for as long as possible each day, and then slept in tents in between two cabins if need be. Even though Mr. Day agreed that reaching the destination as quickly as possible was desirable, he was not willing to sacrifice the comfort of a proper bed.

After a fierce argument, Mr. Day and Dr. Knight decided to split up, each to follow their own strategy. Assuming they both walk at the same pace, how long will Dr. Knight need to wait at the final destination before Mr. Day shows up?

-----Input-----
The first line of input contains two integers, $n$ ($1 \leq n \leq 100000$) the number of cabins, and $m$ ($1 \leq m \leq 100000$) the number of trails. Then follows $m$ lines, each describing a trail. The $i$’th such line contains three integers, $u_ i$, $v_ i$ and $d_ i$ ($0 \leq u_ i, v_ i < n$, $0 \leq d_ i \leq 12$) meaning that there is a trail between cabin $u_ i$ and cabin $v_ i$ which will take exactly $d$ hours to traverse. (There can be more than one trail between two cabins, and some trails could lead back to the same cabin from where it started).

Mr. Day and Dr. Knight start in cabin $0$ and their destination is cabin $n-1$. Each day they start walking at 08:00 in the morning, and then walks non-stop for (at most) $12$ hours before settling down for the night.

-----Output-----
Output a single integer, the number of hours Dr. Knight needs to wait at the destination before Mr. Day shows up.

-----Examples-----
Sample Input:
5 6
0 1 2
0 3 8
1 2 11
2 3 5
2 4 2
4 3 9
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N candies in a room labelled from 1 to N and there are N - 1 directed path between these candies such that every candy has at least 1 path leading to the candy or away from it.

K and L want to eat all the candies in the room but they don't know where to start.

If K starts with the candy labelled c (1 ≤ c ≤ N), then he can eat all the candies which can be reached from the position of the candy c. Similarly, if L starts with the candy labelled d (1 ≤ d ≤ N), then he can eat all the candies which can be reached from the position of the candy d. Note that both, K and L, can start from the same candy position.

Now, they will be able to eat all the candies in the room if there exist candy positions c and d such that any other candy in the room can be eaten by at least one of them. In order to make this possible, they want to change the direction of some number of paths. You have to calculate the minimum number of paths that need to be changed so that K and L can eat all the candies.

Input Format

The first line of input contains the number of candies, N(1 ≤ N ≤ 3000). Each of the next N-1 lines contains 2 space separated integers ai and bi (1 ≤ ai,bi ≤ N; ai != bi) denoting that there exists a directed path from candy  ai to candy bi. Candies are labeled from 1 to N.

Output Format

In the only line of output print the minimum number of paths that need to be changed so that K and L can eat all the candies.

SAMPLE INPUT
4
1 4
2 4
3 4

SAMPLE OUTPUT
1

Explanation

In the sample case, the graph is such that we need to change at least one road to achieve our target. One of the possible ways is to reverse the road from (1, 4) to (4, 1) and then select C, D as 2, 3 respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an strictly convex polygon with n vertices. It is guaranteed that no three points are collinear. You would like to take a maximum non intersecting path on the polygon vertices that visits each point at most once.

More specifically your path can be represented as some sequence of distinct polygon vertices. Your path is the straight line segments between adjacent vertices in order. These segments are not allowed to touch or intersect each other except at the vertices in your sequence.

Given the polygon, print the maximum length non-intersecting path that visits each point at most once.

Input

The first line of input will contain a single integer n (2 ≤ n ≤ 2 500), the number of points.

The next n lines will contain two integers xi, yi (|xi|, |yi| ≤ 109), denoting the coordinates of the i-th vertex.

It is guaranteed that these points are listed in clockwise order.

Output

Print a single floating point number, representing the longest non-intersecting path that visits the vertices at most once.

Your answer will be accepted if it has absolute or relative error at most 10 - 9. More specifically, if your answer is a and the jury answer is b, your answer will be accepted if <image>.

Example

Input

4
0 0
0 1
1 1
1 0


Output

3.4142135624

Note

One optimal path is to visit points 0,1,3,2 in order.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are some stones on Bob's table in a row, and each of them can be red, green or blue, indicated by the characters `R`, `G`, and `B`.

Help Bob find the minimum number of stones he needs to remove from the table so that the stones in each pair of adjacent stones have different colours.

Examples:

```
"RGBRGBRGGB"   => 1
"RGGRGBBRGRR"  => 3
"RRRRGGGGBBBB" => 9
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a weighted tree with n nodes and n-1 edges. The nodes are conveniently labeled from 1 to n. The weights are positive integers at most 100. Define the distance between two nodes to be the sum of edges on the unique path between the nodes. You would like to find the diameter of the tree. Diameter is the maximum distance between a pair of nodes.

Unfortunately, the tree isn't given to you, but you can ask some questions about it. In one question, you can specify two nonempty disjoint sets of nodes p and q, and the judge will return the maximum distance between a node in p and a node in q. In the words, maximum distance between x and y, where x ∈ p and y ∈ q. After asking not more than 9 questions, you must report the maximum distance between any pair of nodes.

Interaction

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 1 000). Description of the test cases follows.

The first line of each test case contains an integer n (2 ≤ n ≤ 100) — the number of nodes in the tree.

To ask a question, print "k_1\ k_2\ a_1\ a_2\ …\ a_{k_1}\ b_1\ b_2\ …\ b_{k_2}" (k_1, k_2 ≥ 1 and k_1+k_2 ≤ n). These two sets must be nonempty and disjoint. The judge will respond with a single integer max_{p,q} dist(a_p, b_q). If you ever get a result of -1 (because you printed an invalid query), exit immediately to avoid getting other verdicts.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



When you are ready to answer, print "-1\ d", where d is the maximum shortest distance over all pairs of nodes.

You can only ask at most 9 questions per test case.

Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer t (t=1).

The second line should contain a single integer n (2 ≤ n ≤ 100).

Each of the next n-1 lines should contain three integers a_i, b_i, c_i (1≤ a_i, b_i≤ n, 1 ≤ c_i ≤ 100). This denotes an undirected edge between nodes a_i and b_i with weight c_i. These edges must form a tree.

Example

Input


2
5
9
6
10
9
10
2
99


Output


1 4 1 2 3 4 5
1 4 2 3 4 5 1
1 4 3 4 5 1 2
1 4 4 5 1 2 3
1 4 5 1 2 3 4
-1 10
1 1 1 2
-1 99

Note

In the first example, the first tree looks as follows: <image>

In the first question, we have p = {1}, and q = {2, 3, 4, 5}. The maximum distance between a node in p and a node in q is 9 (the distance between nodes 1 and 5).

The second tree is a tree with two nodes with an edge with weight 99 between them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Panic is rising in the committee for doggo standardization — the puppies of the new brood have been born multi-colored! In total there are 26 possible colors of puppies in the nature and they are denoted by letters from 'a' to 'z' inclusive.

The committee rules strictly prohibit even the smallest diversity between doggos and hence all the puppies should be of the same color. Thus Slava, the committee employee, has been assigned the task to recolor some puppies into other colors in order to eliminate the difference and make all the puppies have one common color.

Unfortunately, due to bureaucratic reasons and restricted budget, there's only one operation Slava can perform: he can choose a color $x$ such that there are currently at least two puppies of color $x$ and recolor all puppies of the color $x$ into some arbitrary color $y$. Luckily, this operation can be applied multiple times (including zero).

For example, if the number of puppies is $7$ and their colors are represented as the string "abababc", then in one operation Slava can get the results "zbzbzbc", "bbbbbbc", "aaaaaac", "acacacc" and others. However, if the current color sequence is "abababc", then he can't choose $x$='c' right now, because currently only one puppy has the color 'c'.

Help Slava and the committee determine whether it is possible to standardize all the puppies, i.e. after Slava's operations all the puppies should have the same color.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of puppies.

The second line contains a string $s$ of length $n$ consisting of lowercase Latin letters, where the $i$-th symbol denotes the $i$-th puppy's color.


-----Output-----

If it's possible to recolor all puppies into one color, print "Yes".

Otherwise print "No".

Output the answer without quotation signs.


-----Examples-----
Input
6
aabddc

Output
Yes

Input
3
abc

Output
No

Input
3
jjj

Output
Yes



-----Note-----

In the first example Slava can perform the following steps:   take all puppies of color 'a' (a total of two) and recolor them into 'b';  take all puppies of color 'd' (a total of two) and recolor them into 'c';  take all puppies of color 'b' (three puppies for now) and recolor them into 'c'. 

In the second example it's impossible to recolor any of the puppies.

In the third example all the puppies' colors are the same; thus there's no need to recolor anything.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is baking a cake.

While baking, in each minute the size of cake doubles as compared to its previous size.

In this cake, baking of cake is directly proportional to its size.
You are given $a$, the total time taken(in minutes) to bake the whole cake.

Let cake be half baked at $k^{th}$ minute.         
Your task is to find the value of $k+2$.

-----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 and only line of each test case contains a single integer $a$.

-----Output:-----
For each testcase , print one line, the value of $k+2$.

-----Constraints-----
- $1 \leq T \leq 8 $
- $2 \leq a \leq 10^{128}$

-----Sample Input:-----
1

2

-----Sample Output:-----
3

-----Explaination-----
Time was 1 min when cake was half baked by chef so answer is 1+2=3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A molecule consists of atoms that are held together by chemical bonds. Each bond links two atoms together. Each atom may be linked to multiple other atoms, each with a separate chemical bond. All atoms in a molecule are connected to each other via chemical bonds, directly or indirectly.

The chemical properties of a molecule is determined by not only how pairs of atoms are connected by chemical bonds, but also the physical locations of the atoms within the molecule. Chemical bonds can pull atoms toward each other, so it is sometimes difficult to determine the location of the atoms given the complex interactions of all the chemical bonds in a molecule.

You are given the description of a molecule. Each chemical bond connects two distinct atoms, and there is at most one bond between each pair of atoms. The coordinates of some of the atoms are known and fixed, and the remaining atoms naturally move to the locations such that each atom is at the average of the locations of the connected neighboring atoms via chemical bonds. For simplicity, the atoms in the molecule are on the Cartesian $xy$-plane.

-----Input-----
The first line of input consists of two integers $n$ ($2 \leq n \leq 100$), the number of atoms, and $m$ ($n-1 \leq m \leq \frac{n(n-1)}{2}$), the number of chemical bonds.

The next $n$ lines describe the location of the atoms. The $i^\textrm {th}$ of which contains two integers $x, y$ ($0 \leq x,y \leq 1000$ or $x = y = -1$), which are the $x$ and $y$ coordinates of the $i^\textrm {th}$ atom. If both coordinates are $-1$, however, the location of this atom is not known.

The next $m$ lines describe the chemical bonds. The $i^\textrm {th}$ of which contains two integers $a$ and $b$ ($1 \leq a < b \leq n$) indicating that there is a chemical bond between atom $a$ and atom $b$.

It is guaranteed that at least one atom has its location fixed.

-----Output-----
Display $n$ lines that describe the final location of each atom. Specifically, on the $i^\textrm {th}$ such line, display two numbers $x$ and $y$, the final coordinates of the $i^\textrm {th}$ atom. If there are multiple solutions, any of them is accepted. A solution is accepted if the coordinates of each unknown atom and the average coordinates of all its neighboring atoms via chemical bonds differ by at most $10^{-3}$. Note that it is acceptable for multiple atoms to share the same coordinates.

-----Examples-----
Sample Input 1:
3 2
0 0
-1 -1
2 0
1 2
2 3
Sample Output 1:
0 0
1 0
2 0

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

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
One day Vasya got hold of information on the Martian dollar course in bourles for the next *n* days. The buying prices and the selling prices for one dollar on day *i* are the same and are equal to *a**i*. Vasya has *b* bourles. He can buy a certain number of dollars and then sell it no more than once in *n* days. According to Martian laws, one can buy only an integer number of dollars. Which maximal sum of money in bourles can Vasya get by the end of day *n*?

Input Specification:
The first line contains two integers *n* and *b* (1<=≤<=*n*,<=*b*<=≤<=2000) — the number of days and the initial number of money in bourles. The next line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=2000) — the prices of Martian dollars.

Output Specification:
Print the single number — which maximal sum of money in bourles can Vasya get by the end of day *n*.

Demo Input:
['2 4\n3 7\n', '4 10\n4 3 2 1\n', '4 10\n4 2 3 1\n']

Demo Output:
['8\n', '10\n', '15\n']

Note:
none

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