vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Kingdom and its Cities

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Meanwhile, the kingdom of K is getting ready for the marriage of the King's daughter. However, in order not to lose face in front of the relatives, the King should first finish reforms in his kingdom. As the King can not wait for his daughter's marriage, reforms must be finished as soon as possible.

The kingdom currently consists of *n* cities. Cities are connected by *n*<=-<=1 bidirectional road, such that one can get from any city to any other city. As the King had to save a lot, there is only one path between any two cities.

What is the point of the reform? The key ministries of the state should be relocated to distinct cities (we call such cities important). However, due to the fact that there is a high risk of an attack by barbarians it must be done carefully. The King has made several plans, each of which is described by a set of important cities, and now wonders what is the best plan.

Barbarians can capture some of the cities that are not important (the important ones will have enough protection for sure), after that the captured city becomes impassable. In particular, an interesting feature of the plan is the minimum number of cities that the barbarians need to capture in order to make all the important cities isolated, that is, from all important cities it would be impossible to reach any other important city.

Help the King to calculate this characteristic for each of his plan.

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=≤<=100<=000) — the number of cities in the kingdom.

Each of the next *n*<=-<=1 lines contains two distinct integers *u**i*, *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*) — the indices of the cities connected by the *i*-th road. It is guaranteed that you can get from any city to any other one moving only along the existing roads.

The next line contains a single integer *q* (1<=≤<=*q*<=≤<=100<=000) — the number of King's plans.

Each of the next *q* lines looks as follows: first goes number *k**i* — the number of important cities in the King's plan, (1<=≤<=*k**i*<=≤<=*n*), then follow exactly *k**i* space-separated pairwise distinct numbers from 1 to *n* — the numbers of important cities in this plan.

The sum of all *k**i*'s does't exceed 100<=000.

Output Specification:
For each plan print a single integer — the minimum number of cities that the barbarians need to capture, or print <=-<=1 if all the barbarians' attempts to isolate important cities will not be effective.

Demo Input:
['4\n1 3\n2 3\n4 3\n4\n2 1 2\n3 2 3 4\n3 1 2 4\n4 1 2 3 4\n', '7\n1 2\n2 3\n3 4\n1 5\n5 6\n5 7\n1\n4 2 4 6 7\n']

Demo Output:
['1\n-1\n1\n-1\n', '2\n']

Note:
In the first sample, in the first and the third King's plan barbarians can capture the city 3, and that will be enough. In the second and the fourth plans all their attempts will not be effective.

In the second sample the cities to capture are 3 and 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call an undirected graph G = (V, E) relatively prime if and only if for each edge (v, u) ∈ E GCD(v, u) = 1 (the greatest common divisor of v and u is 1). If there is no edge between some pair of vertices v and u then the value of GCD(v, u) doesn't matter. The vertices are numbered from 1 to |V|.

Construct a relatively prime graph with n vertices and m edges such that it is connected and it contains neither self-loops nor multiple edges.

If there exists no valid graph with the given number of vertices and edges then output "Impossible".

If there are multiple answers then print any of them.

Input

The only line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of vertices and the number of edges.

Output

If there exists no valid graph with the given number of vertices and edges then output "Impossible".

Otherwise print the answer in the following format:

The first line should contain the word "Possible".

The i-th of the next m lines should contain the i-th edge (v_i, u_i) of the resulting graph (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i). For each pair (v, u) there can be no more pairs (v, u) or (u, v). The vertices are numbered from 1 to n.

If there are multiple answers then print any of them.

Examples

Input

5 6


Output

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


Input

6 12


Output

Impossible

Note

Here is the representation of the graph from the first example: <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rarity is designing new clothes, and she is looking for some inspiration! Recently, she learned about the importance of symmetry, and is trying to find ways to incorporate this idea into her designs.

To learn more about symmetry, she decided to search for inspiration in a naturally-symmetric concept, palindromes. A palindrome is a string that reads the same forwards and backwards. For example, peep and deified are palindromes, while tepee and defied are not.

A substring of a string is a string that can be formed by removing zero or more characters from the start and end of the other string. For example, sig and design are substrings of design, while dig and signed are not.

Rarity wants to find the perfect amount of symmetry to incorporate into her new design; to this end, she wants to find a string consisting only of lowercase Latin alphabet characters that
 - has length exactly $N$,
 - has exactly $K$ distinct characters, and
 - whose longest palindromic substring has length exactly $P$.

Help her find any string that satisfies all her requirements, or tell her that what she wants is impossible.

-----Input-----
The first and only line of input contains exactly three integers, $N$ ($1 \leq N \leq 10^6$), $K$ ($1 \leq K \leq 26$) and $P$ ($1 \leq P \leq N$), the requirements of the string.

-----Output-----
Output on a line by itself:
 - a string satisfying all her requirements, if any such string exists, or
 - IMPOSSIBLE, otherwise.

If there are multiple correct answers, you can output any of them.

-----Examples-----
Sample Input 1:
6 5 3
Sample Output 1:
rarity

Sample Input 2:
9 8 1
Sample Output 2:
canterlot

Sample Input 3:
5 3 5
Sample Output 3:
madam

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This challenge extends the previous [repeater()](https://www.codewars.com/kata/thinkful-string-drills-repeater) challenge. Just like last time, your job is to write a function that accepts a string and a number as arguments. This time, however, you should format the string you return like this:
```python
>>> repeater('yo', 3)
'"yo" repeated 3 times is: "yoyoyo"'
>>> repeater('WuB', 6)
'"WuB" repeated 6 times is: "WuBWuBWuBWuBWuBWuB"'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is a teacher responsible for a class of N students.
The students are given distinct student numbers from 1 to N.
Today, all the students entered the classroom at different times.
According to Takahashi's record, there were A_i students in the classroom when student number i entered the classroom (including student number i).
From these records, reconstruct the order in which the students entered the classroom.

-----Constraints-----
 -  1 \le N \le 10^5 
 -  1 \le A_i \le N 
 -  A_i \neq A_j  (i \neq j)
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_N

-----Output-----
Print the student numbers of the students in the order the students entered the classroom.

-----Sample Input-----
3
2 3 1

-----Sample Output-----
3 1 2

First, student number 3 entered the classroom.
Then, student number 1 entered the classroom.
Finally, student number 2 entered the classroom.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When Serezha was three years old, he was given a set of cards with letters for his birthday. They were arranged into words in the way which formed the boy's mother favorite number in binary notation. Serezha started playing with them immediately and shuffled them because he wasn't yet able to read. His father decided to rearrange them. Help him restore the original number, on condition that it was the maximum possible one. 

Input

The first line contains a single integer n (1 ⩽ n ⩽ 10^5) — the length of the string. The second line contains a string consisting of English lowercase letters: 'z', 'e', 'r', 'o' and 'n'.

It is guaranteed that it is possible to rearrange the letters in such a way that they form a sequence of words, each being either "zero" which corresponds to the digit 0 or "one" which corresponds to the digit 1.

Output

Print the maximum possible number in binary notation. Print binary digits separated by a space. The leading zeroes are allowed.

Examples

Input


4
ezor


Output


0 


Input


10
nznooeeoer


Output


1 1 0 

Note

In the first example, the correct initial ordering is "zero".

In the second example, the correct initial ordering is "oneonezero".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a permutation $p$ of length $n$, find its subsequence $s_1$, $s_2$, $\ldots$, $s_k$ of length at least $2$ such that:  $|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$ is as big as possible over all subsequences of $p$ with length at least $2$.  Among all such subsequences, choose the one whose length, $k$, is as small as possible. 

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deleting some (possibly, zero or all) elements.

A permutation of length $n$ is an array of length $n$ in which every element from $1$ to $n$ occurs exactly once.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 10^5$) — the length of the permutation $p$.

The second line of each test case contains $n$ integers $p_1$, $p_2$, $\ldots$, $p_{n}$ ($1 \le p_i \le n$, $p_i$ are distinct) — the elements of the permutation $p$.

The sum of $n$ across the test cases doesn't exceed $10^5$.


-----Output-----

For each test case, the first line should contain the length of the found subsequence, $k$. The second line should contain $s_1$, $s_2$, $\ldots$, $s_k$ — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.


-----Example-----
Input
2
3
3 2 1
4
1 3 4 2

Output
2
3 1 
3
1 4 2 



-----Note-----

In the first test case, there are $4$ subsequences of length at least $2$:  $[3,2]$ which gives us $|3-2|=1$.  $[3,1]$ which gives us $|3-1|=2$.  $[2,1]$ which gives us $|2-1|=1$.  $[3,2,1]$ which gives us $|3-2|+|2-1|=2$. 

So the answer is either $[3,1]$ or $[3,2,1]$. Since we want the subsequence to be as short as possible, the answer is $[3,1]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In 2N - 1 boxes there are apples and oranges. Your task is to choose N boxes so, that they will contain not less than half of all the apples and not less than half of all the oranges.

Input

The first input line contains one number T — amount of tests. The description of each test starts with a natural number N — amount of boxes. Each of the following 2N - 1 lines contains numbers ai and oi — amount of apples and oranges in the i-th box (0 ≤ ai, oi ≤ 109). The sum of N in all the tests in the input doesn't exceed 105. All the input numbers are integer.

Output

For each test output two lines. In the first line output YES, if it's possible to choose N boxes, or NO otherwise. If the answer is positive output in the second line N numbers — indexes of the chosen boxes. Boxes are numbered from 1 in the input order. Otherwise leave the second line empty. Separate the numbers with one space.

Examples

Input

2
2
10 15
5 7
20 18
1
0 0


Output

YES
1 3
YES
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a square matrix of integer numbers. Rotate it 90 degrees clockwise (see examples for clarification of rotation).

Input

The input consists of n lines (1 ≤ n ≤ 10, n is not given explicitly). Each of the lines contains n space-separated integers; j-th integer in i-th line corresponds to matrix element mij (1 ≤ mij ≤ 100).

Output

Output the rotated matrix in the same format as the input.

Examples

Input

1 2 3
4 5 6
7 8 9


Output

7 4 1
8 5 2
9 6 3


Input

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16


Output

13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The wide mouth frog is particularly interested in the eating habits of other creatures.

He just can't stop asking the creatures he encounters what they like to eat. But then he meet the alligator who just LOVES to eat wide-mouthed frogs!

When he meets the alligator, it then makes a tiny mouth.

Your goal in this kata is to create complete the `mouth_size` method this method take one argument `animal` which corresponds to the animal encountered by frog. If this one is an `alligator` (case insensitive) return `small` otherwise return `wide`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of n elements, update all elements of given array to some minimum value x i.e, arr[i] = x (0 <= i < n), such that product of all elements of this new array is strictly greater than the product of all elements of the initial array.
Example 1:
Input:
N=5
arr[] = {4, 2, 1, 10, 6} 
Output: 4
Explanation:
4 is the smallest value such that  
4 * 4 * 4 * 4 * 4 > 4 * 2 * 1 * 10 * 6.  
Example 2:
Input:
N=5
arr[] = {100, 150, 10000, 123458, 90980454} 
Output: 17592
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function findMinValue() that takes array arr and n as parameters and return the desired minimum value.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}
 1 <= arr[i] <= 10^{10}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day John had to take care of his little nephew Jim. He was very busy, so he gave Jim a big bag full of building bricks. The bricks are of various heights: at most 15 different heights. For each height, the bag contains infinitely many bricks. 

Now, Jim’s task is to build every possible tower of height $N$ from the given bricks. Bricks are stacked vertically only and stand in an upright position. Two towers are different if their brick height sequences are different.

Jim is good at building towers and can build one tower in exactly 2 minutes, regardless of its height. John wants to know the time Jim requires to build all possible towers.  

Input Format 

There are $3$ lines of input. First line contains an integer, $N$, the height of tower to be built. Second line contains another integer, $\mbox{K}$, which represents different heights of bricks available in the bag. Third line contains $\mbox{K}$ distinct integers representing the available heights.  

Output Format 

In one line print the number of minutes Jim requires to build all possible towers. As this number can be very large, print the number modulo $(10^9+7)$.  

Constraints 

$1\leq N\leq10^{18}$ 

$1\leq K\leq15$ 

All heights will be unique. 

Height of each brick will lie in range [1, 15].  

Sample Input#00

10
1
1

Sample Output#00  

2

Explanation#00:  There is exactly one type of brick, so there is exactly one tower of height 10. Building any tower takes 2 minutes, so the answer is 2.

Sample Input#01  

5
2
2 3

Sample Output#01  

4

Explanation #01: There are two types of bricks. There are two different towers of height 5 which can be build from these types of bricks: $[2,3]$ and $[3,2]$. They are different, because the sequence of bricks in them is different. Building any tower takes 2 minutes, so the answer is $2\times2=4$.

Sample Input#03  

19
2
4 5

Sample Output#03

8

Explanation #03: There are two types of bricks. Jim can build 4 different towers of height $19$ from these bricks: $[5,5,5,4]$, $[5,5,4,5]$, $[5,4,5,5]$ and $[4,5,5,5]$. Building any tower takes 2 minutes, so the answer is $2\times4=8$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yoshi is a frog. He lives in the ZOO under a log which was specially transported there from a distant equatorial rainforest. The log is big and wet and attracts the flies and that is what makes Yoshi satisfied.

There is also a line of pebbles which runs through the wetland in front of the log. There are various dark spots on the pebbles and sometimes Yoshi likes to look at them and dream that they are not just spots but some really big flies instead.

Yesterday, Yoshi’s friend camel Addawser came to see him and suggested to play a game.

“Do you see those spots on the pebbles?” asked Addawser. “I challenge you to start on the leftmost pebble and then do some jumps from a pebble to another pebble but with some restrictions. You can jump from a pebble to another one only if the sum of numbers of spots on both pebbles is equal to the distance between the pebbles. And you have to get to as distant pebble as possible.”

“All right, but you know that I can count at most to twenty three and no more,” hesitated Yoshi.

“No problem, I will help you with the bigger numbers,” said Addawser.

“Then, it’s easy,” said Yoshi, positioning himself on the first pebble and looking inquisitively over the rest of the line. “Although, one might not be quite so sure, after all,” he added after a while.

You are given the sequence of numbers of dark spots on the pebbles in the line. You are asked to find the most distant pebble which can be reached by a sequence of jumps. The first jump starts at the first pebble in the line and a jump between two pebbles is possible if and only if the sum of numbers of spots on both pebbles is equal to the distance between them. You may suppose that the line of pebbles is straight and that the distance between each two neighboring pebbles is exactly one frog distance unit.

-----Input-----
Each case starts with a line containing one integer $N$ ($1 \leq N \leq 1000000$) representing the number of pebbles. The second line contains a list of $N$ integers. The order of the integers in the list is the same as the order of the pebbles in the wetland, each integer represents the number of spots on the corresponding pebble. No pebble contains more than $10^9$ spots. Suppose that Addawser knows all different pairs of pebbles where Yoshi can perform a jump from one pebble to another one during his sequence of jumps. You are guaranteed that the number of those pairs of pebbles never exceeds $1000000$.

-----Output-----
Print a single line with one integer denoting the distance of the pebble which can be reached by successive jumps according to the given rules and which is the most distant from the first pebble.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every email consists of a local name and a domain name, separated by the @ sign.
For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.
Besides lowercase letters, these emails may contain '.'s or '+'s.
If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name.  For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address.  (Note that this rule does not apply for domain names.)
If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com.  (Again, this rule does not apply for domain names.)
It is possible to use both of these rules at the same time.
Given a list of emails, we send one email to each address in the list.  How many different addresses actually receive mails? 
 

Example 1:
Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

 
Note:

1 <= emails[i].length <= 100
1 <= emails.length <= 100
Each emails[i] contains exactly one '@' character.
All local and domain names are non-empty.
Local names do not start with a '+' character.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef appeared for a placement test. 

There is a problem worth X points. Chef finds out that the problem has exactly 10 test cases. It is known that each test case is worth the same number of points. 

Chef passes N test cases among them. Determine the score Chef will get.

NOTE: See sample explanation for more clarity.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, two integers X and N, the total points for the problem and the number of test cases which pass for Chef's solution.

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

For each test case, output the points scored by Chef.

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

$1 ≤ T ≤ 100$
$10 ≤ X ≤ 200$
$0 ≤ N ≤ 10$
$X$ is a multiple of $10$.

----- Sample Input 1 ------ 
4
10 3
100 10
130 4
70 0

----- Sample Output 1 ------ 
3
100
52
0

----- explanation 1 ------ 
Test Case $1$: The problem is worth $10$ points and since there are $10$ test cases, each test case is worth $1$ point. Since Chef passes $3$ test cases, his score will be $1 \cdot 3 = 3$ points.

Test Case $2$: The problem is worth $100$ points and since there are $10$ test cases, each test case is worth $10$ points. Since Chef passes all the $10$ test cases, his score will be $10 \cdot 10 = 100$ points.

Test Case $3$: The problem is worth $130$ points and since there are $10$ test cases, each test case is worth $13$ points. Since Chef passes $4$ test cases, his score will be $13 \cdot 4 = 52$ points.

Test Case $4$: The problem is worth $70$ points and since there are $10$ test cases, each test case is worth $7$ points. Since Chef passes $0$ test cases, his score will be $7 \cdot 0 = 0$ points.

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