vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A bicycle race is being organized in a land far, far away. There are $N$ towns in the land, numbered $1$ through $N$. There are also $M$ one-way roads between the towns. The race will start in town $1$ and end in town $2$.

How many different ways can the route be set? Two routes are considered different if they do not use the exact same roads.

-----Input-----
The first line of input contains two integers $N$ and $M$ ($1 \le N \le 10000$, $1 \le M \le 100000$), the number of towns and roads.

Each of the next $M$ lines contains two different integers $A$ and $B$, representing a road from town $A$ to town $B$.

Towns may be connected by more than one road.

-----Output-----
Output the number of distinct routes that can be set on a single line. If that number has more than nine digits, output only the last nine digits of the number. If there are infinitely many routes, output “inf”.

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

Sample Input 2:
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3
Sample Output 2:
inf

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given an array of unique elements, and your task is to rerrange the values so that the first max value is followed by the first minimum, followed by second max value then second min value, etc. 

For example:
The first max is `15` and the first min is `7`. The second max is `12` and the second min is `10` and so on. 

More examples in the test cases. 

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The process of mammoth's genome decoding in Berland comes to its end!

One of the few remaining tasks is to restore unrecognized nucleotides in a found chain s. Each nucleotide is coded with a capital letter of English alphabet: 'A', 'C', 'G' or 'T'. Unrecognized nucleotides are coded by a question mark '?'. Thus, s is a string consisting of letters 'A', 'C', 'G', 'T' and characters '?'.

It is known that the number of nucleotides of each of the four types in the decoded genome of mammoth in Berland should be equal.

Your task is to decode the genome and replace each unrecognized nucleotide with one of the four types so that the number of nucleotides of each of the four types becomes equal.


-----Input-----

The first line contains the integer n (4 ≤ n ≤ 255) — the length of the genome.

The second line contains the string s of length n — the coded genome. It consists of characters 'A', 'C', 'G', 'T' and '?'.


-----Output-----

If it is possible to decode the genome, print it. If there are multiple answer, print any of them. If it is not possible, print three equals signs in a row: "===" (without quotes).


-----Examples-----
Input
8
AG?C??CT

Output
AGACGTCT

Input
4
AGCT

Output
AGCT

Input
6
????G?

Output
===

Input
4
AA??

Output
===



-----Note-----

In the first example you can replace the first question mark with the letter 'A', the second question mark with the letter 'G', the third question mark with the letter 'T', then each nucleotide in the genome would be presented twice.

In the second example the genome is already decoded correctly and each nucleotide is exactly once in it.

In the third and the fourth examples it is impossible to decode the genom.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's assume we need "clean" strings. Clean means a string should only contain letters `a-z`, `A-Z` and spaces. We assume that there are no double spaces or line breaks.

Write a function that takes a string and returns a string without the unnecessary characters.

### Examples

```python
remove_chars('.tree1')    ==> 'tree'

remove_chars("that's a pie$ce o_f p#ie!")  ==> 'thats a piece of pie'

remove_chars('john.dope@dopington.com')    ==> 'johndopedopingtoncom'

remove_chars('my_list = ["a","b","c"]')    ==> 'mylist  abc'

remove_chars('1 + 1 = 2')    ==> '    ' (string with 4 spaces)

remove_chars("0123456789(.)+,|[]{}=@/~;^$'<>?-!*&:#%_")  ==> '' (empty string)
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!

Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset. 

To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed $1$.

Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found here.


-----Input-----

The first line contains the number of vertices $n$ ($2 \le n \le 700$).

The second line features $n$ distinct integers $a_i$ ($2 \le a_i \le 10^9$) — the values of vertices in ascending order.


-----Output-----

If it is possible to reassemble the binary search tree, such that the greatest common divisor of any two vertices connected by the edge is greater than $1$, print "Yes" (quotes for clarity).

Otherwise, print "No" (quotes for clarity).


-----Examples-----
Input
6
3 6 9 18 36 108

Output
Yes

Input
2
7 17

Output
No

Input
9
4 8 10 12 15 18 33 44 81

Output
Yes



-----Note-----

The picture below illustrates one of the possible trees for the first example. [Image] 

The picture below illustrates one of the possible trees for the third example. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef has a recipe he wishes to use for his guests,
but the recipe will make far more food than he can serve to the guests.
The chef therefore would like to make a reduced version of the recipe which has the same ratios of ingredients, but makes less food.
The chef, however, does not like fractions.
The original recipe contains only whole numbers of ingredients,
and the chef wants the reduced recipe to only contain whole numbers of ingredients as well.
Help the chef determine how much of each ingredient to use in order to make as little food as possible.

-----Input-----
Input will begin with an integer T, the number of test cases.
Each test case consists of a single line.
The line begins with a positive integer N, the number of ingredients.
N integers follow, each indicating the quantity of a particular ingredient that is used.

-----Output-----
For each test case, output exactly N space-separated integers on a line,
giving the quantity of each ingredient that the chef should use in order to make as little food as possible.

-----Sample Input-----
3
2 4 4
3 2 3 4
4 3 15 9 6

-----Sample Output-----
1 1
2 3 4
1 5 3 2

-----Constraints-----
T≤100

2≤N≤50

All ingredient quantities are between 1 and 1000, inclusive.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Abhi and his friends (Shanky,Anku and Pandey) love to play with strings. Abhi invented a simple game. He will give a string S to his friends. Shanky and Anku will play the game while Pandey is just a spectator. Shanky will traverse the string from beginning (left to right) while Anku will traverse from last (right to left). Both have to find the first character they encounter during their traversal,that appears only once in the entire string. Winner will be one whose character is alphabetically more superior(has higher ASCII value). When it is not possible to decide the winner by comparing their characters, Pandey will be the winner.

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains a string S having only lowercase alphabets ( a..z ).

Output
For each test case, output a single line containing "SHANKY" if Shanky is the winner or "ANKU" if Anku is the winner or "PANDEY" if the winner is Pandey. Output your answer without quotes.

Constraints

1 ≤ T ≤ 100
1 < |S| ≤ 10^5


Example
Input:
3
google
breakraekb
aman

Output:
SHANKY
PANDEY
ANKU


Explanation
Example case 2. Both Shanky and Anku can not find any such character. Hence it is not possible to decide the winner between these two. So Pandey is the winner.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
.remove(x)
  
This operation removes element $\boldsymbol{x}$ from the set. 

If element $\boldsymbol{x}$ does not exist, it raises a KeyError.

The .remove(x) operation returns None.

Example

>>> s = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> s.remove(5)
>>> print s
set([1, 2, 3, 4, 6, 7, 8, 9])
>>> print s.remove(4)
None
>>> print s
set([1, 2, 3, 6, 7, 8, 9])
>>> s.remove(0)
KeyError: 0

.discard(x)
  
This operation also removes element $\boldsymbol{x}$ from the set. 

If element $\boldsymbol{x}$ does not exist, it does not raise a KeyError.

The .discard(x) operation returns None.

Example

>>> s = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> s.discard(5)
>>> print s
set([1, 2, 3, 4, 6, 7, 8, 9])
>>> print s.discard(4)
None
>>> print s
set([1, 2, 3, 6, 7, 8, 9])
>>> s.discard(0)
>>> print s
set([1, 2, 3, 6, 7, 8, 9])

.pop()
  
This operation removes and return an arbitrary element from the set. 

If there are no elements to remove, it raises a KeyError.

Example

>>> s = set([1])
>>> print s.pop()
1
>>> print s
set([])
>>> print s.pop()
KeyError: pop from an empty set
  
Task
  
You have a non-empty set $\boldsymbol{\mathrm{~S~}}$, and you have to execute $N$ commands given in $N$ lines.

The commands will be pop, remove and discard. 

Input Format

The first line contains integer $n$, the number of elements in the set $\boldsymbol{\mathrm{~S~}}$. 

The second line contains $n$ space separated elements of set $\boldsymbol{\mathrm{~S~}}$. All of the elements are non-negative integers, less than or equal to 9. 

The third line contains integer $N$, the number of commands.

The next $N$ lines contains either pop, remove and/or discard commands followed by their associated value.

Constraints

$0<n<20$ 

$\boldsymbol{0<N<20}$

Output Format

Print the sum of the elements of set $\boldsymbol{\mathrm{~S~}}$ on a single line.

Sample Input
9
1 2 3 4 5 6 7 8 9
10
pop
remove 9
discard 9
discard 8
remove 7
pop 
discard 6
remove 5
pop 
discard 5

Sample Output
4

Explanation

After completing these $10$ operations on the set, we get set$\left([4]\right)$. Hence, the sum is $\begin{array}{c}4\end{array}$.

Note: Convert the elements of set s to integers while you are assigning them. To ensure the proper input of the set, we have added the first two lines of code to the editor.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
- Percent sign sand dollar sign! And colon semicolon, too!

 - You Asterisk-mouth! – Sam & Max: Hit the Road 

When typing SMS messages on a mobile phone, each of the ten digit buttons represent several alphabetic characters. On my phone (an ancient Ericsson T65, in case anyone was wondering), I have the following mapping (1 is used for space, and 0 for some common non-alphabetic symbols):

2 $\rightarrow $ ABC

3 $\rightarrow $ DEF

4 $\rightarrow $ GHI

5 $\rightarrow $ JKL

6 $\rightarrow $ MNO

7 $\rightarrow $ PQRS

8 $\rightarrow $ TUV

9 $\rightarrow $ WXYZ

As you’ve probably experienced, this makes the typing quite cumbersome. The phones usually try to compensate this by making use of a dictionary – basically, the idea is that there will typically be relatively few actual words having the same button combination. The way this works is that when you have typed a certain digit sequence, you can cycle through the words in the dictionary that map to this digit sequence using the “up” and “down” buttons. Pressing “up” gives you the next word, and pressing “down” gives you the previous word. Words are ordered by how common they are, most common words first and least common words last. This wraps, so that pressing “up” at the last word gives you the first word and similarly for “down”. Initially after having pressed a digit sequence, you will get the first (most common) word that maps to this sequence.

This usually works quite well, but if you’re trying to type a word that does not exist in the dictionary, you have to write it by separating it into several parts, where each part is a word in the dictionary. In order to start writing a new part, you have to press the “right” button on the keypad.

Obviously, the number of keys needed to type a word depends on how (and if) we divide it into parts. Now, I would like to know how to type a word (that may or may not be from the dictionary) using as few key presses as possible (it’s not that I’m lazy, I just want to decrease the wear and tear of my keypad).

-----Input-----
The input begins with an integer $1 \le N \le 200000$ giving the size of the dictionary, followed by $N$ lines, giving the words of the dictionary from most common to least common. Words consist solely of lower case ’a’-’z’ and are at most 10 characters long.

Then follows an integer $1 \le Q \le 1000$ giving the number of words to type. This is followed by $Q$ lines, each containing a nonempty word to type. It will always be possible to type the given words using the given dictionary. The total length of all $Q$ words to type will be at most $500000$.

-----Output-----
For each query, output a line containing any optimal keypress solution in the following format.
 - For pressing any of the digits 2-9, simply output that digit.
 - For pressing right, output ’R’.
 - For pressing up or down $x > 0$ times, output “U($x$)” or “D($x$)”, respectively.

Note that the minimum number of keypresses may be very big: it can exceed $2^{32}$.

-----Examples-----
Sample Input:
1
echo
1
echoecho
Sample Output:
3246R3246

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Robot's Task

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Robot Doc is located in the hall, with *n* computers stand in a line, numbered from left to right from 1 to *n*. Each computer contains exactly one piece of information, each of which Doc wants to get eventually. The computers are equipped with a security system, so to crack the *i*-th of them, the robot needs to collect at least *a**i* any pieces of information from the other computers. Doc can hack the computer only if he is right next to it.

The robot is assembled using modern technologies and can move along the line of computers in either of the two possible directions, but the change of direction requires a large amount of resources from Doc. Tell the minimum number of changes of direction, which the robot will have to make to collect all *n* parts of information if initially it is next to computer with number 1.

It is guaranteed that there exists at least one sequence of the robot's actions, which leads to the collection of all information. Initially Doc doesn't have any pieces of information.

Input Specification:
The first line contains number *n* (1<=≤<=*n*<=≤<=1000). The second line contains *n* non-negative integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=&lt;<=*n*), separated by a space. It is guaranteed that there exists a way for robot to collect all pieces of the information.

Output Specification:
Print a single number — the minimum number of changes in direction that the robot will have to make in order to collect all *n* parts of information.

Demo Input:
['3\n0 2 0\n', '5\n4 2 3 0 1\n', '7\n0 3 1 0 5 2 6\n']

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

Note:
In the first sample you can assemble all the pieces of information in the optimal manner by assembling first the piece of information in the first computer, then in the third one, then change direction and move to the second one, and then, having 2 pieces of information, collect the last piece.

In the second sample to collect all the pieces of information in the optimal manner, Doc can go to the fourth computer and get the piece of information, then go to the fifth computer with one piece and get another one, then go to the second computer in the same manner, then to the third one and finally, to the first one. Changes of direction will take place before moving from the fifth to the second computer, then from the second to the third computer, then from the third to the first computer.

In the third sample the optimal order of collecting parts from computers can look like that: 1-&gt;3-&gt;4-&gt;6-&gt;2-&gt;5-&gt;7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.



Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

* '.' - a black tile
* '#' - a red tile
* '@' - a man on a black tile(appears exactly once in a data set)


The end of the input is indicated by a line consisting of two zeros.

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Examples

Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0


Output

45
59
6
13


Input

6 9
....#.
.....#
......
......
......
......
......
@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
.###
...@...
.###
..#.#..
..#.#..
0 0


Output

45
59
6
13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to use the Amidakuji to improve luck by gaining the ability to read the future. Of course, not only relying on intuition, but also detailed probability calculation is indispensable.

The Amidakuji we consider this time consists of N vertical bars with a length of H + 1 cm. The rabbit looks at the top of the stick and chooses one of the N. At the bottom of the bar, "hit" is written only at the location of the Pth bar from the left. The Amidakuji contains several horizontal bars. Consider the following conditions regarding the arrangement of horizontal bars.

* Each horizontal bar is at a height of a centimeter from the top of the vertical bar, where a is an integer greater than or equal to 1 and less than or equal to H.
* Each horizontal bar connects only two adjacent vertical bars.
* There are no multiple horizontal bars at the same height.



The rabbit drew M horizontal bars to satisfy these conditions. Unfortunately, the rabbit has a good memory, so I remember all the hit positions and the positions of the horizontal bars, so I can't enjoy the Amidakuji. So I decided to have my friend's cat add more horizontal bars.

First, the rabbit chooses one of the N sticks, aiming for a hit. After that, the cat performs the following operations exactly K times.

* Randomly select one of the locations that meet the conditions specified above even if a horizontal bar is added. Here, it is assumed that every place is selected with equal probability. Add a horizontal bar at the selected location.



Then, it is determined whether the stick selected by the rabbit was a hit. The way to follow the bars is the same as the normal Amidakuji (every time you meet a horizontal bar, you move to the next vertical bar). Rabbits want to have a high probability of winning as much as possible.



Input


H N P M K
A1 B1
...
AM BM


In Ai, Bi (1 ≤ i ≤ M), the i-th horizontal bar drawn by the rabbit is at a height of Ai centimeters from the top of the vertical bar, and the second vertical bar from the left and Bi from the left. + An integer that represents connecting the first vertical bar.

2 ≤ H ≤ 500, 2 ≤ N ≤ 100, 1 ≤ P ≤ N, 1 ≤ M ≤ 100, 1 ≤ K ≤ 100, M + K ≤ H, 1 ≤ A1 <A2 <... <AM ≤ H, Satisfy 1 ≤ Bi ≤ N-1.

Output

Output the probability of winning in one line when the rabbit chooses a stick so that the probability of winning is maximized. Absolute errors of 10-6 or less are allowed.

Examples

Input

9 4 3 2 1
2 1
7 3


Output

0.571428571


Input

9 4 3 2 3
2 1
7 3


Output

0.375661376

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a complete directed graph $K_n$ with $n$ vertices: each pair of vertices $u \neq v$ in $K_n$ have both directed edges $(u, v)$ and $(v, u)$; there are no self-loops.

You should find such a cycle in $K_n$ that visits every directed edge exactly once (allowing for revisiting vertices).

We can write such cycle as a list of $n(n - 1) + 1$ vertices $v_1, v_2, v_3, \dots, v_{n(n - 1) - 1}, v_{n(n - 1)}, v_{n(n - 1) + 1} = v_1$ — a visiting order, where each $(v_i, v_{i + 1})$ occurs exactly once.

Find the lexicographically smallest such cycle. It's not hard to prove that the cycle always exists.

Since the answer can be too large print its $[l, r]$ segment, in other words, $v_l, v_{l + 1}, \dots, v_r$.


-----Input-----

The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases.

Next $T$ lines contain test cases — one per line. The first and only line of each test case contains three integers $n$, $l$ and $r$ ($2 \le n \le 10^5$, $1 \le l \le r \le n(n - 1) + 1$, $r - l + 1 \le 10^5$) — the number of vertices in $K_n$, and segment of the cycle to print.

It's guaranteed that the total sum of $n$ doesn't exceed $10^5$ and the total sum of $r - l + 1$ doesn't exceed $10^5$.


-----Output-----

For each test case print the segment $v_l, v_{l + 1}, \dots, v_r$ of the lexicographically smallest cycle that visits every edge exactly once.


-----Example-----
Input
3
2 1 3
3 3 6
99995 9998900031 9998900031

Output
1 2 1 
1 3 2 3 
1 



-----Note-----

In the second test case, the lexicographically minimum cycle looks like: $1, 2, 1, 3, 2, 3, 1$.

In the third test case, it's quite obvious that the cycle should start and end in vertex $1$.

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