vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Table bowling tournament participant completed the competition according to the given final standings table. The table is given as a sequence of lines, each line has a format "name score". Your task is to prepare another table consisting of lines in the form "place name". Sort participant by score (desc.) and by the name lexicographically in the case of a tie. Places are numerated from 1. If more than one participant has some score, all of them share the places and you should output something like "12-14 john".

Please, look into the samples for clarification.

Input

The first line contains n (1 ≤ n ≤ 100) — the number of rows in the table. Following n lines contain the given table. Each line has the form "name score", where "name" is a sequence of lowercase Latin letters, and "score" — is an integer number between 0 and 1000, inclusive. All the names are distinct. The length of each name is between 1 and 10 characters, inclusive. There is single space between the name and the score in each line.

Output

Print the required table. Look at the sample outputs for clarifications.

Examples

Input

5
vasya 10
ted 11
petya 10
katya 33
mike 44


Output

1 mike
2 katya
3 ted
4-5 petya
4-5 vasya


Input

3
a 1
b 13
c 1


Output

1 b
2-3 a
2-3 c

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Shortest Path Problem?

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an undirected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is traversed more than once, then it is included in bitwise xor the same number of times). You have to find the minimum length of path between vertex 1 and vertex *n*.

Note that graph can contain multiple edges and loops. It is guaranteed that the graph is connected.

Input Specification:
The first line contains two numbers *n* and *m* (1<=≤<=*n*<=≤<=100000, *n*<=-<=1<=≤<=*m*<=≤<=100000) — the number of vertices and the number of edges, respectively.

Then *m* lines follow, each line containing three integer numbers *x*, *y* and *w* (1<=≤<=*x*,<=*y*<=≤<=*n*, 0<=≤<=*w*<=≤<=108). These numbers denote an edge that connects vertices *x* and *y* and has weight *w*.

Output Specification:
Print one number — the minimum length of path between vertices 1 and *n*.

Demo Input:
['3 3\n1 2 3\n1 3 2\n3 2 0\n', '2 2\n1 1 3\n1 2 3\n']

Demo Output:
['2\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Divya's watch of worth Rs10 cr is abducted by N thieves(1,2....i...N). The fight over the watch leads to a final decision that it should belong to the thief who wins a simple game. The rules of the game state that every thief  registers a time in the format HH:MM:SS . Accordingly the average A of three clockwise angles  between the hours , minutes and seconds hands is calculated . Thus the ith thief  with the maximum A wins the game and gets to keep the watch.

The thieves are poor in mathematics and will need your help . Given the number of thieves and their registered time resolves the conflict and help them in choosing the winner 

-----Input-----
First line of input contains T which denotes the number of test cases.

The first line of each test case consists of an integer which denotes the number of thieves thereby N line follow which give the time choosen by each thieve in the format HH:MM:SS.

-----Output:-----
Output single integer i which denotes the ith thief.

-----Constraints:-----

1<=T<=100

1<=N<=50

01<=HH<=12

00<=MM<=60

00<=SS<=60

-----Example:-----
Input:
2
3
12:28:26
07:26:04
11:23:17
2
07:43:25
06:23:34

Output:
3
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has a deposit of 100 yen (the currency of Japan) in AtCoder Bank.
The bank pays an annual interest rate of 1 % compounded annually. (A fraction of less than one yen is discarded.)
Assuming that nothing other than the interest affects Takahashi's balance, in how many years does the balance reach X yen or above for the first time?

-----Constraints-----
 -  101 \le X \le 10^{18} 
 - All values in input are integers.

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

-----Output-----
Print the number of years it takes for Takahashi's balance to reach X yen or above for the first time.

-----Sample Input-----
103

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

 - The balance after one year is 101 yen.
 - The balance after two years is 102 yen.
 - The balance after three years is 103 yen.
Thus, it takes three years for the balance to reach 103 yen or above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A wise man told Kerem "Different is good" once, so Kerem wants all things in his life to be different. 

Kerem recently got a string s consisting of lowercase English letters. Since Kerem likes it when things are different, he wants all substrings of his string s to be distinct. Substring is a string formed by some number of consecutive characters of the string. For example, string "aba" has substrings "" (empty substring), "a", "b", "a", "ab", "ba", "aba".

If string s has at least two equal substrings then Kerem will change characters at some positions to some other lowercase English letters. Changing characters is a very tiring job, so Kerem want to perform as few changes as possible.

Your task is to find the minimum number of changes needed to make all the substrings of the given string distinct, or determine that it is impossible.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 100 000) — the length of the string s.

The second line contains the string s of length n consisting of only lowercase English letters.


-----Output-----

If it's impossible to change the string s such that all its substring are distinct print -1. Otherwise print the minimum required number of changes.


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

Output
1

Input
4
koko

Output
2

Input
5
murat

Output
0



-----Note-----

In the first sample one of the possible solutions is to change the first character to 'b'.

In the second sample, one may change the first character to 'a' and second character to 'b', so the string becomes "abko".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
William arrived at a conference dedicated to cryptocurrencies. Networking, meeting new people, and using friends' connections are essential to stay up to date with the latest news from the world of cryptocurrencies.

The conference has $n$ participants, who are initially unfamiliar with each other. William can introduce any two people, $a$ and $b$, who were not familiar before, to each other.

William has $d$ conditions, $i$'th of which requires person $x_i$ to have a connection to person $y_i$. Formally, two people $x$ and $y$ have a connection if there is such a chain $p_1=x, p_2, p_3, \dots, p_k=y$ for which for all $i$ from $1$ to $k - 1$ it's true that two people with numbers $p_i$ and $p_{i + 1}$ know each other.

For every $i$ ($1 \le i \le d$) William wants you to calculate the maximal number of acquaintances one person can have, assuming that William satisfied all conditions from $1$ and up to and including $i$ and performed exactly $i$ introductions. The conditions are being checked after William performed $i$ introductions. The answer for each $i$ must be calculated independently. It means that when you compute an answer for $i$, you should assume that no two people have been introduced to each other yet.


-----Input-----

The first line contains two integers $n$ and $d$ ($2 \le n \le 10^3, 1 \le d \le n - 1$), the number of people, and number of conditions, respectively.

Each of the next $d$ lines each contain two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n, x_i \neq y_i$), the numbers of people which must have a connection according to condition $i$.


-----Output-----

Output $d$ integers. $i$th number must equal the number of acquaintances the person with the maximal possible acquaintances will have, if William performed $i$ introductions and satisfied the first $i$ conditions.


-----Examples-----

Input
7 6
1 2
3 4
2 4
7 6
6 5
1 7
Output
1
1
3
3
3
6
Input
10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4
Output
1
2
3
4
5
5
6
8


-----Note-----

The explanation for the first test case:

In this explanation, the circles and the numbers in them denote a person with the corresponding number. The line denotes that William introduced two connected people. The person marked with red has the most acquaintances. These are not the only correct ways to introduce people.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
King Cambyses loves Fibonacci numbers. He has several armies. Today he wants to make a new army for himself and he wants the number of men in this army to be the n-th Fibonacci number.

Given n you should find n-th Fibonacci number. The set of Fibonacci numbers start with f0 = f1 = 1 and for each i ≥ 2, fi = fi - 1 + fi - 2.

Input

Input contains a single integer n (1 ≤ n ≤ 20).

Output

Write a single integer. The n-th Fibonacci number.

Examples

Input

2


Output

2


Input

1


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Python, a string can be split on a delimiter.  

Example:  

>>> a = "this is a string"
>>> a = a.split(" ") # a is converted to a list of strings. 
>>> print a
['this', 'is', 'a', 'string']

Joining a string is simple:  

>>> a = "-".join(a)
>>> print a
this-is-a-string 

Task 

You are given a string. Split the string on a " " (space) delimiter and join using a - hyphen.   

Function Description   

Complete the split_and_join function in the editor below.   

split_and_join has the following parameters:   

string line: a string of space-separated words   

Returns   

string: the resulting string   

Input Format 

The one line contains a string consisting of space separated words.  

Sample Input 

this is a string   

Sample Output  

this-is-a-string

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a canvas divided into a grid with H rows and W columns. The square at the i-th row from the top and the j-th column from the left is represented as (i, j).
Initially, all the squares are white. square1001 wants to draw a picture with black paint. His specific objective is to make Square (i, j) black when s_{i, j}= `#`, and to make Square (i, j) white when s_{i, j}= `.`.
However, since he is not a good painter, he can only choose two squares that are horizontally or vertically adjacent and paint those squares black, for some number of times (possibly zero). He may choose squares that are already painted black, in which case the color of those squares remain black.
Determine if square1001 can achieve his objective.

Constraints

* H is an integer between 1 and 50 (inclusive).
* W is an integer between 1 and 50 (inclusive).
* For every (i, j) (1 \leq i \leq H, 1 \leq j \leq W), s_{i, j} is `#` or `.`.

Input

Input is given from Standard Input in the following format:


H W
s_{1, 1} s_{1, 2} s_{1, 3} ... s_{1, W}
s_{2, 1} s_{2, 2} s_{2, 3} ... s_{2, W}
:   :
s_{H, 1} s_{H, 2} s_{H, 3} ... s_{H, W}


Output

If square1001 can achieve his objective, print `Yes`; if he cannot, print `No`.

Examples

Input

3 3
.#.
###
.#.


Output

Yes


Input

3 3
.#.

.#.


Output

Yes


Input

5 5
.#.#
.#.#.
.#.#
.#.#.
.#.#


Output

No


Input

11 11
...#####...
.##.....##.
..##.##..#
..##.##..#
.........#
...###...#
.#########.
.#.#.#.#.#.
.#.#.#.##
..##.#.##..
.##..#..##.


Output

Yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the free-market, ruthlessly capitalist world of train fares, only one thing matters: incentives.

Train companies are incentivised with bonuses for high throughput, successful journeys, and customer satisfaction. Conversely, the companies are disincentivised from failure via mandatory refunds for customers delayed by $30$ minutes or more.

Being a ruthless capitalist yourself, you have decided to take advantage of this generous delay compensation provision.

The refund is awarded provided that no matter the combination of trains you had taken (provided they followed the same route of stations as planned), you would still be unable to reach your destination in strictly less time than $30$ minutes (or $1800$ seconds), of the time you would have arrived assuming your booked journey was exactly on time.

Armed with your printout of the day’s delays, and the original timetable, you must ask yourself only one question: what is the earliest time you can book a train for from station $1$, in order to earn this restitutive reward?

-----Input-----
 - One line containing two integers: $N$ ($1 \le N \le 100$), the number of stations, and $M$ ($1 \le M \le 10^5$), the number of scheduled trains.
 - The next $M$ lines each contain 4 integers:
 - $X$, the starting station ($1 \le X \le N-1$),
 - $S$ and $T$ ($0 \le S \le T < 86400$), the planned departure and arrival times in seconds,
 - and $L$ ($0 \le L < 86400$), the duration by which the train’s departure and arrival times are delayed.

Stations are numbered from $1$ to $N$ in the order you will visit them. Each train goes between stations $X$ and $X+1$. It is possible to change between trains instantanesouly.

-----Output-----
 - One line containing one integer: the start time of the earliest train journey you could book in order to earn your compensation, or impossible if no such journey is possible.

-----Examples-----
Sample Input 1:
2 3
1 1800 9000 1800
1 2000 9200 1600
1 2200 9400 1400
Sample Output 1:
1800

Sample Input 2:
2 2
1 1800 3600 1800
1 1900 3600 1600
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are an adventurer currently journeying inside an evil temple. After defeating a couple of weak zombies, you arrived at a square room consisting of tiles forming an n × n grid. The rows are numbered 1 through n from top to bottom, and the columns are numbered 1 through n from left to right. At the far side of the room lies a door locked with evil magical forces. The following inscriptions are written on the door: The cleaning of all evil will awaken the door! 

Being a very senior adventurer, you immediately realize what this means. You notice that every single cell in the grid are initially evil. You should purify all of these cells.

The only method of tile purification known to you is by casting the "Purification" spell. You cast this spell on a single tile — then, all cells that are located in the same row and all cells that are located in the same column as the selected tile become purified (including the selected tile)! It is allowed to purify a cell more than once.

You would like to purify all n × n cells while minimizing the number of times you cast the "Purification" spell. This sounds very easy, but you just noticed that some tiles are particularly more evil than the other tiles. You cannot cast the "Purification" spell on those particularly more evil tiles, not even after they have been purified. They can still be purified if a cell sharing the same row or the same column gets selected by the "Purification" spell.

Please find some way to purify all the cells with the minimum number of spells cast. Print -1 if there is no such way.


-----Input-----

The first line will contain a single integer n (1 ≤ n ≤ 100). Then, n lines follows, each contains n characters. The j-th character in the i-th row represents the cell located at row i and column j. It will be the character 'E' if it is a particularly more evil cell, and '.' otherwise.


-----Output-----

If there exists no way to purify all the cells, output -1. Otherwise, if your solution casts x "Purification" spells (where x is the minimum possible number of spells), output x lines. Each line should consist of two integers denoting the row and column numbers of the cell on which you should cast the "Purification" spell.


-----Examples-----
Input
3
.E.
E.E
.E.

Output
1 1
2 2
3 3

Input
3
EEE
E..
E.E

Output
-1

Input
5
EE.EE
E.EE.
E...E
.EE.E
EE.EE

Output
3 3
1 3
2 2
4 4
5 3


-----Note-----

The first example is illustrated as follows. Purple tiles are evil tiles that have not yet been purified. Red tile is the tile on which "Purification" is cast. Yellow tiles are the tiles being purified as a result of the current "Purification" spell. Green tiles are tiles that have been purified previously.  [Image] 

In the second example, it is impossible to purify the cell located at row 1 and column 1.

For the third example: [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Information technologies are developing and are increasingly penetrating into all spheres of human activity. Incredible as it is, the most modern technology are used in farming!

A large farm has a meadow with grazing sheep. Overall there are n sheep and each of them contains a unique number from 1 to n — because the sheep need to be distinguished and you need to remember information about each one, and they are so much alike! The meadow consists of infinite number of regions numbered from 1 to infinity. It's known that sheep i likes regions from li to ri.

There are two shepherds taking care of the sheep: First and Second. First wakes up early in the morning and leads the sheep graze on the lawn. Second comes in the evening and collects all the sheep.

One morning, First woke up a little later than usual, and had no time to lead the sheep graze on the lawn. So he tied together every two sheep if there is a region they both like. First thought that it would be better — Second would have less work in the evening, because sheep won't scatter too much, being tied to each other!

In the evening Second came on the lawn, gathered the sheep and tried to line them up in a row. But try as he might, the sheep wouldn't line up as Second want! Second had neither the strength nor the ability to untie the sheep so he left them as they are, but with one condition: he wanted to line up the sheep so that the maximum distance between two tied sheep was as small as possible. The distance between the sheep is the number of sheep in the ranks that are between these two.

Help Second find the right arrangement.

Input

The first input line contains one integer n (1 ≤ n ≤ 2000). Each of the following n lines contains two integers li and ri (1 ≤ li, ri ≤ 109; li ≤ ri).

Output

In the single output line print n space-separated numbers — the sought arrangement of the sheep. The i-th value in the line must represent the number of the sheep that took the i-th place from left in the optimal arrangement line. 

If there are multiple optimal arrangements, print any of them.

Examples

Input

3
1 3
5 7
2 4


Output

1 3 2

Input

5
1 5
2 4
3 6
1 7
2 6


Output

2 1 3 5 4

Input

4
1 3
4 6
5 7
2 3


Output

1 4 2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of ints, return the index such that the sum of the elements to the right of that index equals the sum of the elements to the left of that index. If there is no such index, return `-1`. If there is more than one such index, return the left-most index.

For example: 
```
peak([1,2,3,5,3,2,1]) = 3, because the sum of the elements at indexes 0,1,2 == sum of elements at indexes 4,5,6. We don't sum index 3.
peak([1,12,3,3,6,3,1]) = 2
peak([10,20,30,40]) = -1
```

The special case of an array of zeros (for instance `[0,0,0,0]`) will not be tested. 

More examples in the test cases. 

Good luck!

Please also try [Simple time difference](https://www.codewars.com/kata/5b76a34ff71e5de9db0000f2)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During the archaeological research in the Middle East you found the traces of three ancient religions: First religion, Second religion and Third religion. You compiled the information on the evolution of each of these beliefs, and you now wonder if the followers of each religion could coexist in peace.

The Word of Universe is a long word containing the lowercase English characters only. At each moment of time, each of the religion beliefs could be described by a word consisting of lowercase English characters.

The three religions can coexist in peace if their descriptions form disjoint subsequences of the Word of Universe. More formally, one can paint some of the characters of the Word of Universe in three colors: $1$, $2$, $3$, so that each character is painted in at most one color, and the description of the $i$-th religion can be constructed from the Word of Universe by removing all characters that aren't painted in color $i$.

The religions however evolve. In the beginning, each religion description is empty. Every once in a while, either a character is appended to the end of the description of a single religion, or the last character is dropped from the description. After each change, determine if the religions could coexist in peace.


-----Input-----

The first line of the input contains two integers $n, q$ ($1 \leq n \leq 100\,000$, $1 \leq q \leq 1000$) — the length of the Word of Universe and the number of religion evolutions, respectively. The following line contains the Word of Universe — a string of length $n$ consisting of lowercase English characters.

Each of the following line describes a single evolution and is in one of the following formats:   + $i$ $c$ ($i \in \{1, 2, 3\}$, $c \in \{\mathtt{a}, \mathtt{b}, \dots, \mathtt{z}\}$: append the character $c$ to the end of $i$-th religion description.  - $i$ ($i \in \{1, 2, 3\}$) – remove the last character from the $i$-th religion description. You can assume that the pattern is non-empty. 

You can assume that no religion will have description longer than $250$ characters.


-----Output-----

Write $q$ lines. The $i$-th of them should be YES if the religions could coexist in peace after the $i$-th evolution, or NO otherwise.

You can print each character in any case (either upper or lower).


-----Examples-----
Input
6 8
abdabc
+ 1 a
+ 1 d
+ 2 b
+ 2 c
+ 3 a
+ 3 b
+ 1 c
- 2

Output
YES
YES
YES
YES
YES
YES
NO
YES

Input
6 8
abbaab
+ 1 a
+ 2 a
+ 3 a
+ 1 b
+ 2 b
+ 3 b
- 1
+ 2 z

Output
YES
YES
YES
YES
YES
NO
YES
NO



-----Note-----

In the first example, after the 6th evolution the religion descriptions are: ad, bc, and ab. The following figure shows how these descriptions form three disjoint subsequences of the Word of Universe: $\left. \begin{array}{|c|c|c|c|c|c|c|} \hline \text{Word} & {a} & {b} & {d} & {a} & {b} & {c} \\ \hline ad & {a} & {} & {d} & {} & {} & {} \\ \hline bc & {} & {b} & {} & {} & {} & {c} \\ \hline ab & {} & {} & {} & {a} & {b} & {} \\ \hline \end{array} \right.$

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