vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Two semifinals have just been in the running tournament. Each semifinal had n participants. There are n participants advancing to the finals, they are chosen as follows: from each semifinal, we choose k people (0 ≤ 2k ≤ n) who showed the best result in their semifinals and all other places in the finals go to the people who haven't ranked in the top k in their semifinal but got to the n - 2k of the best among the others.

The tournament organizers hasn't yet determined the k value, so the participants want to know who else has any chance to get to the finals and who can go home.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of participants in each semifinal.

Each of the next n lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 10^9) — the results of the i-th participant (the number of milliseconds he needs to cover the semifinals distance) of the first and second semifinals, correspondingly. All results are distinct. Sequences a_1, a_2, ..., a_{n} and b_1, b_2, ..., b_{n} are sorted in ascending order, i.e. in the order the participants finished in the corresponding semifinal.


-----Output-----

Print two strings consisting of n characters, each equals either "0" or "1". The first line should correspond to the participants of the first semifinal, the second line should correspond to the participants of the second semifinal. The i-th character in the j-th line should equal "1" if the i-th participant of the j-th semifinal has any chances to advance to the finals, otherwise it should equal a "0".


-----Examples-----
Input
4
9840 9920
9860 9980
9930 10020
10040 10090

Output
1110
1100

Input
4
9900 9850
9940 9930
10000 10020
10060 10110

Output
1100
1100



-----Note-----

Consider the first sample. Each semifinal has 4 participants. The results of the first semifinal are 9840, 9860, 9930, 10040. The results of the second semifinal are 9920, 9980, 10020, 10090.  If k = 0, the finalists are determined by the time only, so players 9840, 9860, 9920 and 9930 advance to the finals.  If k = 1, the winners from both semifinals move to the finals (with results 9840 and 9920), and the other places are determined by the time (these places go to the sportsmen who run the distance in 9860 and 9930 milliseconds).  If k = 2, then first and second places advance from each seminfial, these are participants with results 9840, 9860, 9920 and 9980 milliseconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ravi, a student of a primary class, is unable to understand the ranking system of his school.
The ranking system is as:

If two students of the class get equal marks, they are given the same rank but students with different marks are given the rank as the (number of students above him + 1). See the example for more clarity.

There are five students in a class. Their marks distribution is:
98 68 74 21 74

That is first student gets marks 98, second gets 68, and so on.
Now , the highest marks is 98. So, the first student gets rank 1.
Next higher marks is 74. So student 3 and 5 gets rank 2.
Next higher marks is 68 and there are three students (1,3,5) who have got marks higher than him. So he gets rank 4.
Similarly , student with marks 21 gets rank 5.

Given marks distribution array of a class, you have to print the ranks of the students.

Input:
The first line consists of the number of test cases(T).
The next line consists of the number of students in the class(n).
The third line consists of the marks distribution array(A[]).

Output:
One line consisting array corresponding to rank of each student of the class.

Constraints:
1≤T≤50
1≤n≤10^4
1≤A[i]≤10^9   1≤i≤n

Example:

Input:
1
5
98 68 74 21 74

Output:
1 4 2 5 2

SAMPLE INPUT
1
5
98 68 74 21 74

SAMPLE OUTPUT
1 4 2 5 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It’s another day in the office, and you’re a mastermind of not doing any work yourself. Instead, you’ll go to your coworkers for “help,” but secretly have them do all the work.

You’ve determined that the more one of your coworkers helps you, the more annoyed they become. You’ve also been able to determine how much more annoyed a coworker gets everytime you ask them for help. At the beginning of the day, a coworker is initially $a$ annoyed at you. That’s their annoyance level. Everytime you ask them for help though, they become $d$ more annoyed at you – their annoyance level $a$ increases by a constant amount $d$ so that $a=a+d$.

You want to complete a project of $h$ tasks solely with “help” from your coworkers, but you need to be careful not to annoy any of them too much.

What’s the best you can do?

-----Input-----
The first line contains $2$ integers $h$ and $c$, where $h$ ($1 \le h \le 100000$) is the number of times you have to ask for help to complete the project, and $c$ ($1 \le c \le 100000$) denotes the number of coworkers you have.

Each of the following $c$ lines contains two positive integers $a$ and $d$, representing a coworker whose initial annoyance level is $a$ and who is getting more annoyed at you by an increase of $d$ every time you ask them for help ($1\le a, d \le 10^9$).

-----Output-----
Output a single number, which is the maximum annoyance level any coworker has at you provided you use an optimal strategy to minimize this level. (In other words, of all possible strategies, choose one that minimizes the annoyance level of the worker or workers who are most annoyed at you at the end.)

-----Sample Input 1 Explanation-----
You have $4$ coworkers and you need to ask for help $4$ times. Initially, their annoyance levels are $a_1=1, a_2=2, a_3=3, a_4=4$, the increases are $d_1=2, d_2=3, d_3=4, d_4=5$. One optimal solution is to ask for help twice from coworker $1$, once from coworker $2$, and once from coworker $3$, in which case the final annoyance levels are: $a_1=1 + 2 \cdot 2 = 5, a_2=2 + 3 = 5, a_3=3 + 4 = 7, a_4=4$. The coworker that is most annoyed at you is coworker $3$, whose annoyance level at you is $7$. Or, you could ask coworker $1$ for help $3$ times and coworker $2$ once, leaving you with $a_1=1 + 3 \cdot 2 = 7, a_2=2 + 3 = 5, a_3=3, a_4=4$. Both strategies yield the same minimal maximum amount.

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

Sample Input 2:
3 2
1 1000
1000 1
Sample Output 2:
1002

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N pieces of ropes, numbered 1 through N. The length of piece i is a_i.

At first, for each i (1≤i≤N-1), piece i and piece i+1 are tied at the ends, forming one long rope with N-1 knots. Snuke will try to untie all of the knots by performing the following operation repeatedly:

* Choose a (connected) rope with a total length of at least L, then untie one of its knots.



Is it possible to untie all of the N-1 knots by properly applying this operation? If the answer is positive, find one possible order to untie the knots.

Constraints

* 2≤N≤10^5
* 1≤L≤10^9
* 1≤a_i≤10^9
* All input values are integers.

Input

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


N L
a_1 a_2 ... a_n


Output

If it is not possible to untie all of the N-1 knots, print `Impossible`.

If it is possible to untie all of the knots, print `Possible`, then print another N-1 lines that describe a possible order to untie the knots. The j-th of those N-1 lines should contain the index of the knot that is untied in the j-th operation. Here, the index of the knot connecting piece i and piece i+1 is i.

If there is more than one solution, output any.

Examples

Input

3 50
30 20 10


Output

Possible
2
1


Input

2 21
10 10


Output

Impossible


Input

5 50
10 20 30 40 50


Output

Possible
1
2
3
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an input sequence. You have to write a program to sort it in non decreasing order.

Input
First line of input T has number of test cases followed by T test cases.
Each test case has two lines. First line has a number N. The second line has N space separated elements as an input sequence

Output
Output has T lines of output corresponding to each test case.
Each line will have space separated integers in non decreasing order.

Example

Input:
3
2
3 4
5
1 4 5 8 2
1
7

Output:
3 4
1 2 4 5 8
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem you are given a string s consisting of uppercase and lowercase Latin letters, spaces, dots and commas. Your task is to correct the formatting of this string by removing and inserting spaces, as well as changing the case of the letters.

After formatting, the resulting string must meet the following requirements:

  * the string must not start with a space; 
  * there should be exactly one space between any two consecutive words; 
  * there should be a Latin letter immediately before a dot or a comma, and there should be a space immediately after a dot or a comma in the case that there is a word after that dot or comma, otherwise that dot or comma must be the last character in the string; 
  * all letters must be lowercase, except all first letters in the first words of the sentences, they must be capitalized. The first word of a sentence is a word that is either the first word of the string or a word after a dot. 



It is guaranteed that there is at least one letter in the given string between any two punctuation marks (commas and dots are punctuation marks). There is at least one letter before the leftmost punctuation mark.

Input

The first line contains a non-empty string s, consisting of uppercase and lowercase Latin letters, spaces, dots and commas. The length of the given string does not exceed 255. The string is guaranteed to have at least one character other than the space.

Output

Output the corrected string which meets all the requirements described in the statement.

Examples

Input

  hello ,i AM veRy GooD.Boris


Output

Hello, i am very good. Boris


Input

       a. b,   C  .   


Output

A. B, c.

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


A directed acyclic graph (DAG) can be used to represent the ordering of tasks. Tasks are represented by vertices and constraints where one task can begin before another, are represented by edges. For example, in the above example, you can undertake task B after both task A and task B are finished. You can obtain the proper sequence of all the tasks by a topological sort.

Given a DAG $G$, print the order of vertices after the topological sort.

Constraints

* $1 \leq |V| \leq 10,000$
* $0 \leq |E| \leq 100,000$
* There are no parallel edges in $G$
* There are no self loops in $G$

Input

A directed graph $G$ is given in the following format:
$|V|\;|E|$
$s_0 \; t_0$
$s_1 \; t_1$
:
$s_{|E|-1} \; t_{|E|-1}$



$|V|$ is the number of vertices and $|E|$ is the number of edges in the graph. The graph vertices are named with the numbers $0, 1,..., |V|-1$ respectively.

$s_i$ and $t_i$ represent source and target nodes of $i$-th edge (directed).

Output

Print the vertices numbers in order. Print a number in a line.

If there are multiple possible solutions, print any one of them (the solution is judged by a special validator).

Example

Input

6 6
0 1
1 2
3 1
3 4
4 5
5 2


Output

0
3
1
4
5
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's year 2018 and it's Christmas time! Before going for vacations, students of Hogwarts School of Witchcraft and Wizardry had their end semester exams.
$N$ students attended the semester exam. Once the exam was over, their results were displayed as either "Pass" or "Fail" behind their magic jacket which they wore. A student cannot see his/her result but can see everyone else's results. Each of $N$ students count the number of passed students they can see.
Given the number of "Pass" verdicts that each of the $N$ students counted, we have to figure out conclusively, the number of students who failed, or report that there is some inconsistency or that we cannot be sure.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each test case will contain $N$, representing the number of students who attended the exam.
- Next line contains  $N$ spaced integers representing the number of "Pass" counted by each of the $N$ students.

-----Output:-----
- For each test case, output the answer in a single line. 
- If the counts reported by the students are not consistent with each other or if it's not possible to predict the number of failed students from the given input, then print -1.

-----Constraints-----
- $1 \leq T \leq 50$
- $1 \leq N \leq 10^{5}$
- $0 \leq$ Count given by each Student $\leq 10^{5}$

-----Sample Input:-----
1
4
3 2 2 2

-----Sample Output:-----
1

-----EXPLANATION:-----
There are 4 students, and they counted the number of passed students as 3,2,2,2. The first student can see that all others have passed, and all other students can see only 2 students who have passed. Hence, the first student must have failed, and others have all passed. Hence, the answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has his favourite number $n$. He wants to split it to some non-zero digits. It means, that he wants to choose some digits $d_1, d_2, \ldots, d_k$, such that $1 \leq d_i \leq 9$ for all $i$ and $d_1 + d_2 + \ldots + d_k = n$.

Vasya likes beauty in everything, so he wants to find any solution with the minimal possible number of different digits among $d_1, d_2, \ldots, d_k$. Help him!


-----Input-----

The first line contains a single integer $n$ — the number that Vasya wants to split ($1 \leq n \leq 1000$).


-----Output-----

In the first line print one integer $k$ — the number of digits in the partition. Note that $k$ must satisfy the inequality $1 \leq k \leq n$. In the next line print $k$ digits $d_1, d_2, \ldots, d_k$ separated by spaces. All digits must satisfy the inequalities $1 \leq d_i \leq 9$.

You should find a partition of $n$ in which the number of different digits among $d_1, d_2, \ldots, d_k$ will be minimal possible among all partitions of $n$ into non-zero digits. Among such partitions, it is allowed to find any. It is guaranteed that there exists at least one partition of the number $n$ into digits.


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

Output
1
1 
Input
4

Output
2
2 2

Input
27

Output
3
9 9 9



-----Note-----

In the first test, the number $1$ can be divided into $1$ digit equal to $1$.

In the second test, there are $3$ partitions of the number $4$ into digits in which the number of different digits is $1$. This partitions are $[1, 1, 1, 1]$, $[2, 2]$ and $[4]$. Any of these partitions can be found. And, for example, dividing the number $4$ to the digits $[1, 1, 2]$ isn't an answer, because it has $2$ different digits, that isn't the minimum possible number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In AtCoder City, there are three stations numbered 1, 2, and 3.
Each of these stations is operated by one of the two railway companies, A and B. A string S of length 3 represents which company operates each station. If S_i is A, Company A operates Station i; if S_i is B, Company B operates Station i.
To improve the transportation condition, for each pair of a station operated by Company A and one operated by Company B, there will be a bus service connecting them.
Determine if there is a pair of stations that will be connected by a bus service.

-----Constraints-----
 - Each character of S is A or B.
 - |S| = 3

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
If there is a pair of stations that will be connected by a bus service, print Yes; otherwise, print No.

-----Sample Input-----
ABA

-----Sample Output-----
Yes

Company A operates Station 1 and 3, while Company B operates Station 2.
There will be a bus service between Station 1 and 2, and between Station 2 and 3, so print Yes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luba is surfing the Internet. She currently has n opened tabs in her browser, indexed from 1 to n from left to right. The mouse cursor is currently located at the pos-th tab. Luba needs to use the tabs with indices from l to r (inclusive) for her studies, and she wants to close all the tabs that don't belong to this segment as fast as possible.

Each second Luba can either try moving the cursor to the left or to the right (if the cursor is currently at the tab i, then she can move it to the tab max(i - 1, a) or to the tab min(i + 1, b)) or try closing all the tabs to the left or to the right of the cursor (if the cursor is currently at the tab i, she can close all the tabs with indices from segment [a, i - 1] or from segment [i + 1, b]). In the aforementioned expressions a and b denote the minimum and maximum index of an unclosed tab, respectively. For example, if there were 7 tabs initially and tabs 1, 2 and 7 are closed, then a = 3, b = 6.

What is the minimum number of seconds Luba has to spend in order to leave only the tabs with initial indices from l to r inclusive opened?


-----Input-----

The only line of input contains four integer numbers n, pos, l, r (1 ≤ n ≤ 100, 1 ≤ pos ≤ n, 1 ≤ l ≤ r ≤ n) — the number of the tabs, the cursor position and the segment which Luba needs to leave opened.


-----Output-----

Print one integer equal to the minimum number of seconds required to close all the tabs outside the segment [l, r].


-----Examples-----
Input
6 3 2 4

Output
5

Input
6 3 1 3

Output
1

Input
5 2 1 5

Output
0



-----Note-----

In the first test Luba can do the following operations: shift the mouse cursor to the tab 2, close all the tabs to the left of it, shift the mouse cursor to the tab 3, then to the tab 4, and then close all the tabs to the right of it.

In the second test she only needs to close all the tabs to the right of the current position of the cursor.

In the third test Luba doesn't need to do anything.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The Easter Rabbit laid *n* eggs in a circle and is about to paint them. 

Each egg should be painted one color out of 7: red, orange, yellow, green, blue, indigo or violet. Also, the following conditions should be satisfied:
 -  Each of the seven colors should be used to paint at least one egg. -  Any four eggs lying sequentially should be painted different colors. 
Help the Easter Rabbit paint the eggs in the required manner. We know that it is always possible.

Input Specification:
The only line contains an integer *n* — the amount of eggs (7<=≤<=*n*<=≤<=100).

Output Specification:
Print one line consisting of *n* characters. The *i*-th character should describe the color of the *i*-th egg in the order they lie in the circle. The colors should be represented as follows: "R" stands for red, "O" stands for orange, "Y" stands for yellow, "G" stands for green, "B" stands for blue, "I" stands for indigo, "V" stands for violet.

If there are several answers, print any of them.

Demo Input:
['8\n', '13\n']

Demo Output:
['ROYGRBIV\n', 'ROYGBIVGBIVYG\n']

Note:
The way the eggs will be painted in the first sample is shown on the picture:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Prodiggers are quite a cool band and for this reason, they have been the surprise guest at the ENTER festival for the past 80 years. At the beginning of their careers, they weren’t so successful, so they had to spend time digging channels to earn money; hence the name. Anyway, they like to tour a lot and have surprising amounts of energy to do extremely long tours. However, they hate spending two consecutive days without having a concert, so they would like to avoid it.

A tour is defined by a sequence of concerts and days-off. You need to count in how many ways The Prodiggers can select k different tours of the same length between l and r.

For example if k = 2, l = 1 and r = 2, if we define concert day as {1} and day-off as {0}, here are all possible tours: {0}, {1}, {00}, {01}, {10}, {11}. But tour 00 can not be selected because it has 2 days-off in a row. Now, we need to count in how many ways we can select k = 2 tours of the same length in range [1;2]. Here they are: {0,1}; {01,10}; {01,11}; {10,11}.

Since their schedule is quite busy, they want you to tell them in how many ways can do that, modulo 1 000 000 007 (109 + 7).

Input

The first line of the input contains three integers k, l and r (1 ≤ k ≤ 200, 1 ≤ l ≤ r ≤ 1018).

Output

Output a single number: the number of ways to select k different tours of the same length, modulo 1 000 000 007.

Example

Input

1 1 2


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has $N$ points (numbered $1$ through $N$) in a 2D Cartesian coordinate system. For each valid $i$, the $i$-th point is $(x_i, y_i)$. He also has a fixed integer $c$ and he may perform operations of the following type: choose a point $(x_i, y_i)$ and move it to $(x_i + c, y_i + c)$ or $(x_i - c, y_i - c)$.
Now, Chef wants to set up one or more checkpoints (points in the same coordinate system) and perform zero or more operations in such a way that after they are performed, each of his (moved) $N$ points is located at one of the checkpoints.
Chef's primary objective is to minimise the number of checkpoints. Among all options with this minimum number of checkpoints, he wants to choose one which minimises the number of operations he needs to perform.
Can you help Chef find the minimum number of required checkpoints and the minimum number of operations he needs to perform to move all $N$ points to these checkpoints?

-----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 line of each test case contains two space-separated integers $N$ and $c$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $x_i$ and $y_i$.

-----Output-----
For each test case, print a single line containing two integers ― the minimum number of checkpoints and the minimum number of moves.

-----Constraints-----
- $1 \le T \le 5$
- $1 \le N \le 5 \cdot 10^5$
- $|x_i|, |y_i| \le 10^9$ for each valid $i$
- $0 < c \le 10^9$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^5$

-----Example Input-----
1
3 1
1 1
1 0
3 2

-----Example Output-----
2 2

-----Explanation-----
Example case 1: One optimal solution is to set up checkpoints at coordinates $(1, 1)$ and $(1, 0)$. Since the points $(1, 1)$ and $(1, 0)$ are already located at checkpoints, Chef can just move the point $(3, 2)$ to the checkpoint $(1, 0)$ in two moves: $(3, 2) \rightarrow (2, 1) \rightarrow (1, 0)$.

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