vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This problem is interactive.

We have hidden an array a of n pairwise different numbers (this means that no two numbers are equal). You can get some information about this array using a new device you just ordered on Amazon. 

This device can answer queries of the following form: in response to the positions of k different elements of the array, it will return the position and value of the m-th among them in the ascending order.

Unfortunately, the instruction for the device was lost during delivery. However, you remember k, but don't remember m. Your task is to find m using queries to this device. 

You can ask not more than n queries.

Note that the array a and number m are fixed before the start of the interaction and don't depend on your queries. In other words, interactor is not adaptive.

Note that you don't have to minimize the number of queries, and you don't need to guess array a. You just have to guess m.

Input

The first line contains two integers n and k (1≤ k < n ≤ 500) — the length of the array and the number of the elements in the query.

It is guaranteed that number m satisfies 1≤ m ≤ k, elements a_1, a_2, ..., a_n of the array satisfy 0≤ a_i ≤ 10^9, and all of them are different.

Interaction

You begin the interaction by reading n and k.

To ask a question about elements on positions x_1, x_2, ..., x_k, in a separate line output

? x_1 x_2 x_3 ... x_k

Numbers in the query have to satisfy 1 ≤ x_i ≤ n, and all x_i have to be different. Don't forget to 'flush', to get the answer.

In response, you will receive two integers pos and a_{pos} — the position in the array a of the m-th in ascending order element among a_{x_1}, a_{x_2}, ..., a_{x_k}, and the element on this position.

In case your query is invalid or you asked more than n queries, the program will print -1 and will finish interaction. You will receive a Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you determine m, output 

! m

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.



Hack format

For the hacks use the following format:

The first line has to contain three integers n, k, m (1 ≤ m ≤ k < n ≤ 500) — the length of the array, number of elements in the query, and which in the ascending order number the device returns.

In the next line output n integers a_1, a_2, ..., a_n (0≤ a_i ≤ 10^9) — the elements of the array. They have to be pairwise different.

Example

Input


4 3
4 9
4 9
4 9
1 2

Output


? 2 3 4
? 1 3 4
? 1 2 4
? 1 2 3
! 3

Note

In the example, n = 4, k = 3, m = 3, a = [2, 0, 1, 9].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pandu has started learning about sub-sets. His teacher gave him a simple work. Given a list of numbers, Pandu has to choose the sub-set which gives the max product. However, the teacher asked Pandu only to submit the max product obtained by taking exactly two numbers from the list. Please help Pandu in finding out the answer to this assignment.

Input Format:

The first line will contain the integer N, the length of the array. The next line contains N space separated integers.

Output Format:

For each test case, output Pandu's query.

Constraints:

2 ≤ N ≤ 105

Subtask 1: (25 points)
0 ≤ Integers ≤ 109

Subtask 2: (75 points)
-109 ≤ Integers ≤ 109

SAMPLE INPUT
2
2 3

SAMPLE OUTPUT
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's denote d(n) as the number of divisors of a positive integer n. You are given three integers a, b and c. Your task is to calculate the following sum:

$\sum_{i = 1}^{a} \sum_{j = 1}^{b} \sum_{k = 1}^{c} d(i \cdot j \cdot k)$

Find the sum modulo 1073741824 (2^30).


-----Input-----

The first line contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 100).


-----Output-----

Print a single integer — the required sum modulo 1073741824 (2^30).


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

Output
20

Input
5 6 7

Output
1520



-----Note-----

For the first example.

  d(1·1·1) = d(1) = 1;  d(1·1·2) = d(2) = 2;  d(1·2·1) = d(2) = 2;  d(1·2·2) = d(4) = 3;  d(2·1·1) = d(2) = 2;  d(2·1·2) = d(4) = 3;  d(2·2·1) = d(4) = 3;  d(2·2·2) = d(8) = 4. 

So the result is 1 + 2 + 2 + 3 + 2 + 3 + 3 + 4 = 20.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp watched TV-show where *k* jury members one by one rated a participant by adding him a certain number of points (may be negative, i. e. points were subtracted). Initially the participant had some score, and each the marks were one by one added to his score. It is known that the *i*-th jury member gave *a**i* points.

Polycarp does not remember how many points the participant had before this *k* marks were given, but he remembers that among the scores announced after each of the *k* judges rated the participant there were *n* (*n*<=≤<=*k*) values *b*1,<=*b*2,<=...,<=*b**n* (it is guaranteed that all values *b**j* are distinct). It is possible that Polycarp remembers not all of the scores announced, i. e. *n*<=&lt;<=*k*. Note that the initial score wasn't announced.

Your task is to determine the number of options for the score the participant could have before the judges rated the participant.

Input Specification:
The first line contains two integers *k* and *n* (1<=≤<=*n*<=≤<=*k*<=≤<=2<=000) — the number of jury members and the number of scores Polycarp remembers.

The second line contains *k* integers *a*1,<=*a*2,<=...,<=*a**k* (<=-<=2<=000<=≤<=*a**i*<=≤<=2<=000) — jury's marks in chronological order.

The third line contains *n* distinct integers *b*1,<=*b*2,<=...,<=*b**n* (<=-<=4<=000<=000<=≤<=*b**j*<=≤<=4<=000<=000) — the values of points Polycarp remembers. Note that these values are not necessarily given in chronological order.

Output Specification:
Print the number of options for the score the participant could have before the judges rated the participant. If Polycarp messes something up and there is no options, print "0" (without quotes).

Demo Input:
['4 1\n-5 5 0 20\n10\n', '2 2\n-2000 -2000\n3998000 4000000\n']

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

Note:
The answer for the first example is 3 because initially the participant could have  - 10, 10 or 15 points.

In the second example there is only one correct initial score equaling to 4 002 000.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
When Sasha was studying in the seventh grade, he started listening to music a lot. In order to evaluate which songs he likes more, he introduced the notion of the song's prettiness. The title of the song is a word consisting of uppercase Latin letters. The prettiness of the song is the prettiness of its title.

Let's define the simple prettiness of a word as the ratio of the number of vowels in the word to the number of all letters in the word.

Let's define the prettiness of a word as the sum of simple prettiness of all the substrings of the word.

More formally, let's define the function *vowel*(*c*) which is equal to 1, if *c* is a vowel, and to 0 otherwise. Let *s**i* be the *i*-th character of string *s*, and *s**i*..*j* be the substring of word *s*, staring at the *i*-th character and ending at the *j*-th character (*s**is**i*<=+<=1... *s**j*, *i*<=≤<=*j*).

Then the simple prettiness of *s* is defined by the formula:

The prettiness of *s* equals 

Find the prettiness of the given song title.

We assume that the vowels are *I*,<=*E*,<=*A*,<=*O*,<=*U*,<=*Y*.

Input Specification:
The input contains a single string *s* (1<=≤<=|*s*|<=≤<=5·105) — the title of the song.

Output Specification:
Print the prettiness of the song with the absolute or relative error of at most 10<=-<=6.

Demo Input:
['IEAIAIO\n', 'BYOB\n', 'YISVOWEL\n']

Demo Output:
['28.0000000\n', '5.8333333\n', '17.0500000\n']

Note:
In the first sample all letters are vowels. The simple prettiness of each substring is 1. The word of length 7 has 28 substrings. So, the prettiness of the song equals to 28.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pushok the dog has been chasing Imp for a few hours already. $48$ 

Fortunately, Imp knows that Pushok is afraid of a robot vacuum cleaner. 

While moving, the robot generates a string t consisting of letters 's' and 'h', that produces a lot of noise. We define noise of string t as the number of occurrences of string "sh" as a subsequence in it, in other words, the number of such pairs (i, j), that i < j and $t_{i} = s$ and $t_{j} = h$. 

The robot is off at the moment. Imp knows that it has a sequence of strings t_{i} in its memory, and he can arbitrary change their order. When the robot is started, it generates the string t as a concatenation of these strings in the given order. The noise of the resulting string equals the noise of this concatenation.

Help Imp to find the maximum noise he can achieve by changing the order of the strings.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of strings in robot's memory.

Next n lines contain the strings t_1, t_2, ..., t_{n}, one per line. It is guaranteed that the strings are non-empty, contain only English letters 's' and 'h' and their total length does not exceed 10^5.


-----Output-----

Print a single integer — the maxumum possible noise Imp can achieve by changing the order of the strings.


-----Examples-----
Input
4
ssh
hs
s
hhhs

Output
18

Input
2
h
s

Output
1



-----Note-----

The optimal concatenation in the first sample is ssshhshhhs.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp likes numbers that are divisible by 3.

He has a huge number $s$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $m$ such cuts, there will be $m+1$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $3$.

For example, if the original number is $s=3121$, then Polycarp can cut it into three parts with two cuts: $3|1|21$. As a result, he will get two numbers that are divisible by $3$.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by $3$ that Polycarp can obtain?


-----Input-----

The first line of the input contains a positive integer $s$. The number of digits of the number $s$ is between $1$ and $2\cdot10^5$, inclusive. The first (leftmost) digit is not equal to 0.


-----Output-----

Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$.


-----Examples-----
Input
3121

Output
2

Input
6

Output
1

Input
1000000000000000000000000000000000

Output
33

Input
201920181

Output
4



-----Note-----

In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by $3$.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and $33$ digits 0. Each of the $33$ digits 0 forms a number that is divisible by $3$.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $0$, $9$, $201$ and $81$ are divisible by $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have k pieces of laundry, each of which you want to wash, dry and fold. You are at a laundromat that has n_1 washing machines, n_2 drying machines and n_3 folding machines. Each machine can process only one piece of laundry at a time. You can't dry a piece of laundry before it is washed, and you can't fold it before it is dried. Moreover, after a piece of laundry is washed, it needs to be immediately moved into a drying machine, and after it is dried, it needs to be immediately moved into a folding machine.

It takes t_1 minutes to wash one piece of laundry in a washing machine, t_2 minutes to dry it in a drying machine, and t_3 minutes to fold it in a folding machine. Find the smallest number of minutes that is enough to wash, dry and fold all the laundry you have.


-----Input-----

The only line of the input contains seven integers: k, n_1, n_2, n_3, t_1, t_2, t_3 (1 ≤ k ≤ 10^4; 1 ≤ n_1, n_2, n_3, t_1, t_2, t_3 ≤ 1000).


-----Output-----

Print one integer — smallest number of minutes to do all your laundry.


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

Output
15

Input
8 4 3 2 10 5 2

Output
32



-----Note-----

In the first example there's one instance of each machine, each taking 5 minutes to complete. You have only one piece of laundry, so it takes 15 minutes to process it.

In the second example you start washing first two pieces at moment 0. If you start the third piece of laundry immediately, then by the time it is dried, there will be no folding machine available, so you have to wait, and start washing third piece at moment 2. Similarly, you can't start washing next piece until moment 5, since otherwise there will be no dryer available, when it is washed. Start time for each of the eight pieces of laundry is 0, 0, 2, 5, 10, 10, 12 and 15 minutes respectively. The last piece of laundry will be ready after 15 + 10 + 5 + 2 = 32 minutes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Little Girl loves problems on games very much. Here's one of them.

Two players have got a string s, consisting of lowercase English letters. They play a game that is described by the following rules:  The players move in turns; In one move the player can remove an arbitrary letter from string s.  If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins. A palindrome is a string that reads the same both ways (from left to right, and vice versa). For example, string "abba" is a palindrome and string "abc" isn't. 

Determine which player will win, provided that both sides play optimally well — the one who moves first or the one who moves second.


-----Input-----

The input contains a single line, containing string s (1 ≤ |s|  ≤  10^3). String s consists of lowercase English letters.


-----Output-----

In a single line print word "First" if the first player wins (provided that both players play optimally well). Otherwise, print word "Second". Print the words without the quotes.


-----Examples-----
Input
aba

Output
First

Input
abca

Output
Second

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A balanced bracket sequence is defined as an integer sequence that can be built with the following rules:

  * The empty sequence is balanced. 
  * If [a_1,…,a_n] and [b_1,…, b_m] are balanced, then their concatenation [a_1,…,a_n,b_1,…,b_m] is balanced. 
  * If x is a positive integer and [a_1,…,a_n] is balanced, then [x,a_1,…,a_n,-x] is balanced. 



The positive numbers can be imagined as opening brackets and the negative numbers as closing brackets, where matching brackets must have the same type (absolute value). For example, [1, 2, -2, -1] and [1, 3, -3, 2, -2, -1] are balanced, but [1, 2, -1, -2] and [-1, 1] are not balanced.

There are 2n cards. Each card has a number on the front and a number on the back. Each integer 1,-1,2,-2,…,n,-n appears exactly once on the front of some card and exactly once on the back of some (not necessarily the same) card.

You can reorder the cards however you like. You are not allowed to flip cards, so numbers cannot move between the front and back. Your task is to order the cards so that the sequences given by the front numbers and the back numbers are both balanced, or report that it is impossible.

Input

The first line contains a single integer n (1≤ n≤ 2⋅ 10^5) — the number of bracket types, and half the number of cards.

The next 2n lines describe the cards. The i-th of these lines contains two integers a_i, b_i (-n≤ a_i,b_i≤ n, a_i≠ 0, b_i≠ 0) — the numbers on the front and back of the i-th card, respectively. Every integer 1,-1,2,-2,…,n,-n appears exactly once as a_i and exactly once as b_i.

Output

On the first line, output "YES" if it's possible to reorder these cards to satisfy the condition. Otherwise, output "NO". You can print each letter in any case (upper or lower).

If it is possible, on the next 2n lines output the cards in an order so that the front and back are both balanced. If there are multiple solutions, you may output any.

Examples

Input


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


Output


YES
1 3
4 -3
-4 4
-1 -4
5 1
3 -1
2 2
-2 5
-3 -5
-5 -2


Input


2
1 1
-1 2
2 -1
-2 -2


Output


NO

Note

In the first test case, the front numbers create the balanced sequence [1,4,-4,-1,5,3,2,-2,-3,-5] and the back numbers create the balanced sequence [3,-3,4,-4,1,-1,2,5,-5,-2].

In the second test case, the cards are given in an order so that the front numbers are balanced, but the back numbers create the unbalanced sequence [1,2,-1,-2]. If we swapped the second and third cards, we would balance the back numbers and unbalance the front numbers. But there is no order that balances both.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef found a strange string yesterday - a string of signs s, where each sign is either a '<', '=' or a '>'. Let N be the length of this string. Chef wants to insert N + 1 positive integers into this sequence and make it valid. A valid sequence is a sequence where every sign is preceded and followed by an integer, and the signs are correct. That is, if a sign '<' is preceded by the integer a and followed by an integer b, then a should be less than b. Likewise for the other two signs as well. 
Chef can take some positive integers in the range [1, P] and use a number in the range as many times as he wants.
Help Chef find the minimum possible P with which he can create a valid sequence.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains the string of signs s, where each sign is either '<', '=' or a '>'. 

-----Output-----
For each test case, output a single line containing an integer corresponding to the minimum possible P. 

-----Constraints-----
- 1 ≤ T, |s| ≤ 105
- 1 ≤ Sum of |s| over all test cases in a single test file ≤ 106

-----Subtasks-----
Subtask #1 (30 points)
- 1 ≤ T, |s| ≤ 103
- 1 ≤ Sum of |s| over all test cases in a single test file ≤ 104

Subtask #2 (70 points)
- Original constraints

-----Example-----
Input:
4
<<<
<><
<=>
<=<

Output:
4
2
2
3

-----Explanation-----
Here are some possible valid sequences which can be formed with the minimum P for each of the test cases:
1 < 2 < 3 < 4
1 < 2 > 1 < 2
1 < 2 = 2 > 1
1 < 2 = 2 < 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a S cm long stick.It can be broken only at certain
positions.Sarah wants to calculate the number of GOOD Pairs.
It satisfies the following conditions
A good pair consists of 2 distinct positions where the stick can be
   broken.
When the stick is broken at these two positions there should be at
    least one stick with length strictly greater than L.

Input:
The first line contains the no. of test cases, t (1 ≤ t ≤ 100).

For each test case,
    The first line of the test case contains three integers :
    S,Length of the stick,3 ≤ S ≤ 5*10^4
    N, total no. of locations where the stick can be broken.
        (2 ≤ N ≤ MIN(S-1,10^4) )
    L, 0 ≤ L ≤ S-1. 
    Next  line contains an N distinct integer array A ,
     It contains the positions where the rod can be broken(in cm)    1 ≤ A[i] ≤ S-1.

Output: Print the no. of GOOD pairs.

SAMPLE INPUT
2
10 2 6
1 3
10 3 5
1 3 9

SAMPLE OUTPUT
1
3

Explanation

For the 1st test case, if the rod is cut at 1cm and 3cm, three rods will
be generated of length 1cm,2cm,7cm.As the third rod's length is greater than 6, it is a GOOD pair.
For the 2nd test case,all three possible pairs will be good pairs

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You start with a value in dollar form, e.g. $5.00. You must convert this value to a string in which the value is said, like '5 dollars' for example. This should account for ones, cents, zeroes, and negative values. Here are some examples:
```python
dollar_to_speech('$0.00') == '0 dollars.'
dollar_to_speech('$1.00') == '1 dollar.'
dollar_to_speech('$0.01') == '1 cent.'
dollar_to_speech('$5.00') == '5 dollars.'
dollar_to_speech('$20.18') == '20 dollars and 18 cents.'
dollar_to_speech('$-1.00') == 'No negative numbers are allowed!'
```
These examples account for pretty much everything. This kata has many specific outputs, so good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jimmy and his friends like to visit large theme parks. In the current theme park there are many roller coasters which then are categorized by Jimmy. He assigns a fun value to each coaster; however, the fun decreases with each run.

More formally: for a specific roller coaster $i$, Jimmy assigns two fun coefficients $a_ i$ and $b_ i$. While riding this roller coaster for the $k$-th time, Jimmy gains a fun value of $f(i,k) = a_ i - (k-1)^2 \cdot b_ i$. If $f(i,k)$ is non-positive, riding the roller coaster is no longer fun.

Jimmy tries to maximize the total fun until he leaves the park. Can you tell Jimmy how much fun he can gain for a given time?

-----Input-----
The input consists of a single test case.

The first line contains the integer $N$, where $N$ is the amount of different roller coasters in the theme park ($0< N\le 100$).

The following $N$ lines contain the integers $a_ i$, $b_ i$ and $t_ i$ where $a_ i$ and $b_ i$ are the fun coefficients as specified above and $t_ i$ is the time for a single ride with the $i$-th roller coaster ($0\le a_ i \le 1000$; $0\le b_ i \le 1000$; $0 < t_ i \le 25000$).

The next line contains a positive integer $Q$ denoting the number of times that Jimmy is visiting the park ($0\le Q \le 1000$). Each of the following $Q$ lines contains an integral time $T_ i$ that Jimmy spends during his $i$-th visit ($0\le T_ i \le 25000$).

-----Output-----
For each of the $Q$ possible times, print one line containing the maximal total fun value if Jimmy spends $T_ i$ minutes in the theme park.

-----Examples-----
Sample Input:
2
5 0 5
7 0 7
4
88
5
6
7
Sample Output:
88
5
5
7

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