vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Rock-paper-scissors

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Uncle Fyodor, Matroskin the Cat and Sharic the Dog live their simple but happy lives in Prostokvashino. Sometimes they receive parcels from Uncle Fyodor’s parents and sometimes from anonymous benefactors, in which case it is hard to determine to which one of them the package has been sent. A photographic rifle is obviously for Sharic who loves hunting and fish is for Matroskin, but for whom was a new video game console meant? Every one of the three friends claimed that the present is for him and nearly quarreled. Uncle Fyodor had an idea how to solve the problem justly: they should suppose that the console was sent to all three of them and play it in turns. Everybody got relieved but then yet another burning problem popped up — who will play first? This time Matroskin came up with a brilliant solution, suggesting the most fair way to find it out: play rock-paper-scissors together. The rules of the game are very simple. On the count of three every player shows a combination with his hand (or paw). The combination corresponds to one of three things: a rock, scissors or paper. Some of the gestures win over some other ones according to well-known rules: the rock breaks the scissors, the scissors cut the paper, and the paper gets wrapped over the stone. Usually there are two players. Yet there are three friends, that’s why they decided to choose the winner like that: If someone shows the gesture that wins over the other two players, then that player wins. Otherwise, another game round is required. Write a program that will determine the winner by the gestures they have shown.

Input Specification:
The first input line contains the name of the gesture that Uncle Fyodor showed, the second line shows which gesture Matroskin showed and the third line shows Sharic’s gesture.

Output Specification:
Print "F" (without quotes) if Uncle Fyodor wins. Print "M" if Matroskin wins and "S" if Sharic wins. If it is impossible to find the winner, print "?".

Demo Input:
['rock\nrock\nrock\n', 'paper\nrock\nrock\n', 'scissors\nrock\nrock\n', 'scissors\npaper\nrock\n']

Demo Output:
['?\n', 'F\n', '?\n', '?\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing a computer card game called Splay the Sire. Currently you are struggling to defeat the final boss of the game.

The boss battle consists of $n$ turns. During each turn, you will get several cards. Each card has two parameters: its cost $c_i$ and damage $d_i$. You may play some of your cards during each turn in some sequence (you choose the cards and the exact order they are played), as long as the total cost of the cards you play during the turn does not exceed $3$. After playing some (possibly zero) cards, you end your turn, and all cards you didn't play are discarded. Note that you can use each card at most once.

Your character has also found an artifact that boosts the damage of some of your actions: every $10$-th card you play deals double damage.

What is the maximum possible damage you can deal during $n$ turns?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of turns.

Then $n$ blocks of input follow, the $i$-th block representing the cards you get during the $i$-th turn.

Each block begins with a line containing one integer $k_i$ ($1 \le k_i \le 2 \cdot 10^5$) — the number of cards you get during $i$-th turn. Then $k_i$ lines follow, each containing two integers $c_j$ and $d_j$ ($1 \le c_j \le 3$, $1 \le d_j \le 10^9$) — the parameters of the corresponding card.

It is guaranteed that $\sum \limits_{i = 1}^{n} k_i \le 2 \cdot 10^5$.


-----Output-----

Print one integer — the maximum damage you may deal.


-----Example-----
Input
5
3
1 6
1 7
1 5
2
1 4
1 3
3
1 10
3 5
2 3
3
1 15
2 4
1 10
1
1 100

Output
263



-----Note-----

In the example test the best course of action is as follows:

During the first turn, play all three cards in any order and deal $18$ damage.

During the second turn, play both cards and deal $7$ damage.

During the third turn, play the first and the third card and deal $13$ damage.

During the fourth turn, play the first and the third card and deal $25$ damage.

During the fifth turn, play the only card, which will deal double damage ($200$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You read scientific research regarding popularity of most famous superstitions across various countries, and you want to analyze their data. More specifically, you want to know which superstitions are popular in most countries.

The data is given as a single file in the following format: country name on a separate line, followed by a list of superstitions popular in it, one entry per line. Each entry of the list is formatted as an asterisk "*" followed by a single space and then by the superstition name. Entries are unique within each country. The first line of input will represent a country. The input will contain at least one superstition. 

Country name is a non-empty sequence of words, where each word consists of only English letters. The words of the name of some country will be separated in input with one or more spaces.

Superstition name is a non-empty sequence of words, where each word consists of only English letters and digits. The words of the name of some superstition will be separated in input with one or more spaces.

You can consider two names equal, if corresponding sequences of words are equal. You shouldn't consider the case of the letters when you compare the words.

Output the list of superstitions which are observed in the greatest number of countries. It's guaranteed that all countries have distinct names.

Input

The input contains between 2 and 50 lines. Every line of input will contain between 1 and 50 characters, inclusive.

No line has leading or trailing spaces.

Output

Output the list of superstitions which are observed in the greatest number of countries in alphabetical order. Each superstition must be converted to lowercase (one superstition can be written with varying capitalization in different countries).

The alphabetical order of superstitions means the lexicographical order of sequences of words (their names).

Examples

Input

Ukraine
* Friday the   13th
* black   cat
* knock the   wood
USA
* wishing well
* friday   the   13th
Holland
France
* Wishing Well


Output

friday the 13th 
wishing well 


Input

Spain
* Tuesday the 13th
Italy
* Friday the 17th
Russia
* Friday the 13th
England
* rabbit foot


Output

friday the 13th 
friday the 17th 
rabbit foot 
tuesday the 13th

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gerald has n younger brothers and their number happens to be even. One day he bought n2 candy bags. One bag has one candy, one bag has two candies, one bag has three candies and so on. In fact, for each integer k from 1 to n2 he has exactly one bag with k candies. 

Help him give n bags of candies to each brother so that all brothers got the same number of candies.

Input

The single line contains a single integer n (n is even, 2 ≤ n ≤ 100) — the number of Gerald's brothers.

Output

Let's assume that Gerald indexes his brothers with numbers from 1 to n. You need to print n lines, on the i-th line print n integers — the numbers of candies in the bags for the i-th brother. Naturally, all these numbers should be distinct and be within limits from 1 to n2. You can print the numbers in the lines in any order. 

It is guaranteed that the solution exists at the given limits.

Examples

Input

2


Output

1 4
2 3

Note

The sample shows Gerald's actions if he has two brothers. In this case, his bags contain 1, 2, 3 and 4 candies. He can give the bags with 1 and 4 candies to one brother and the bags with 2 and 3 to the other brother.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya learned about integer subtraction in school. He is still not very good at it, so he is only able to subtract any single digit number from any other number (which is not necessarily single digit).
For practice, Vasya chose a positive integer n$n$ and wrote it on the first line in his notepad. After that, on the second line he wrote the result of subtraction of the first digit of n$n$ from itself. For example, if n=968$n = 968$, then the second line would contain 968−9=959$968 - 9 = 959$, while with n=5$n = 5$ the second number would be 5−5=0$5 - 5 = 0$. If the second number was still positive, then Vasya would write the result of the same operation on the following line, and so on. For example, if n=91$n = 91$, then the sequence of numbers Vasya would write starts as follows: 91,82,74,67,61,55,50,…$91, 82, 74, 67, 61, 55, 50, \ldots$. One can see that any such sequence eventually terminates with the number 0$0$.
Since then, Vasya lost his notepad. However, he remembered the total number k$k$ of integers he wrote down (including the first number n$n$ and the final number 0$0$). What was the largest possible value of n$n$ Vasya could have started with?

-----Input:-----
The first line contains T$T$ , number of test cases per file.
The only line in each testcase contains a single integer k−$k-$ the total number of integers in Vasya's notepad (2≤k≤1012$2 \leq k \leq 10^{12}$).

-----Output:-----
Print a single integer−$-$ the largest possible value of the starting number n$n$. It is guaranteed that at least one such number n$n$ exists, and the largest possible value is finite.

-----Constraints-----
- 1≤T≤34$1 \leq  T \leq 34 $
- 2≤k≤1012$2 \leq k \leq 10^{12}$

-----Sample Input-----
3
2
3
100

-----Sample Output:-----
9
10
170

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has two ranges [A, B] and [C, D]. Chef needs to find the number of integers that belong to at least one of the ranges.

Note: A range [P, Q] contains all the integers \{P, P+1, P+2, \dots, Q-1, Q\}.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line containing 4 integers A, B, C, and D, as mentioned in the statement.

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

For each test case, output on a new line, the number of integers that belong to at least one of the ranges.

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

$1 ≤ T ≤ 1000$
$1 ≤ A ≤ B ≤ 8$
$1 ≤ C ≤ D ≤ 8$

----- Sample Input 1 ------ 
4
1 3 5 5
3 8 2 5
1 8 4 6
5 5 5 5

----- Sample Output 1 ------ 
4
7
8
1

----- explanation 1 ------ 
Test case $1$: There are $4$ integers that belong to at least one of the ranges. These are $1, 2, 3,$ and $5$.

Test case $2$: There are $7$ integers that belong to at least one of the ranges. These are $2, 3, 4, 5, 6, 7,$ and $8$.

Test case $3$: There are $8$ integers that belong to at least one of the ranges. These are $1, 2, 3, 4, 5, 6, 7,$ and $8$.

Test case $4$: There is only $1$ integer that belong to at least one of the ranges. That integer is $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has a rooted tree with N+1 vertices.
The vertices are numbered 0 through N, and Vertex 0 is the root of the tree.
The parent of Vertex i (1 \leq i \leq N) is Vertex p_i.
Besides this tree, Snuke also has an box which is initially empty and many marbles, and playing with them.
The play begins with placing one marble on some of the vertices, then proceeds as follows:
 - If there is a marble on Vertex 0, move the marble into the box.
 - Move each marble from the vertex to its parent (all at once).
 - For each vertex occupied by two or more marbles, remove all the marbles from the vertex.
 - If there exists a vertex with some marbles, go to Step 1. Otherwise, end the play.
There are 2^{N+1} ways to place marbles on some of the vertices.
For each of them, find the number of marbles that will be in the box at the end of the play, and compute the sum of all those numbers modulo 1,000,000,007.

-----Constraints-----
 - 1 \leq N < 2 \times 10^{5}
 - 0 \leq p_i < i

-----Partial Scores-----
 - In the test set worth 400 points, N < 2{,}000.

-----Input-----
Input is given from Standard Input in the following format:
N
p_1 p_2 ... p_{N}

-----Output-----
Print the answer.

-----Sample Input-----
2
0 0

-----Sample Output-----
8

When we place a marble on both Vertex 1 and 2, there will be multiple marbles on Vertex 0 by step 2. In such a case, these marbles will be removed instead of being moved to the box.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which calculates the distance between two points P1(x1, y1) and P2(x2, y2).



Input

Four real numbers x1, y1, x2 and y2 are given in a line.

Output

Print the distance in real number. The output should not contain an absolute error greater than 10-4.

Example

Input

0 0 1 1


Output

1.41421356

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note that the memory limit in this problem is lower than in others.

You have a vertical strip with n cells, numbered consecutively from 1 to n from top to bottom.

You also have a token that is initially placed in cell n. You will move the token up until it arrives at cell 1.

Let the token be in cell x > 1 at some moment. One shift of the token can have either of the following kinds: 

  * Subtraction: you choose an integer y between 1 and x-1, inclusive, and move the token from cell x to cell x - y. 
  * Floored division: you choose an integer z between 2 and x, inclusive, and move the token from cell x to cell ⌊ x/z ⌋ (x divided by z rounded down). 



Find the number of ways to move the token from cell n to cell 1 using one or more shifts, and print it modulo m. Note that if there are several ways to move the token from one cell to another in one shift, all these ways are considered distinct (check example explanation for a better understanding).

Input

The only line contains two integers n and m (2 ≤ n ≤ 4 ⋅ 10^6; 10^8 < m < 10^9; m is a prime number) — the length of the strip and the modulo.

Output

Print the number of ways to move the token from cell n to cell 1, modulo m.

Examples

Input


3 998244353


Output


5


Input


5 998244353


Output


25


Input


42 998244353


Output


793019428


Input


787788 100000007


Output


94810539

Note

In the first test, there are three ways to move the token from cell 3 to cell 1 in one shift: using subtraction of y = 2, or using division by z = 2 or z = 3.

There are also two ways to move the token from cell 3 to cell 1 via cell 2: first subtract y = 1, and then either subtract y = 1 again or divide by z = 2.

Therefore, there are five ways in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let quasi-palindromic number be such number that adding some leading zeros (possible none) to it produces a palindromic string. 

String t is called a palindrome, if it reads the same from left to right and from right to left.

For example, numbers 131 and 2010200 are quasi-palindromic, they can be transformed to strings "131" and "002010200", respectively, which are palindromes.

You are given some integer number x. Check if it's a quasi-palindromic number.

Input

The first line contains one integer number x (1 ≤ x ≤ 109). This number is given without any leading zeroes.

Output

Print "YES" if number x is quasi-palindromic. Otherwise, print "NO" (without quotes).

Examples

Input

131


Output

YES


Input

320


Output

NO


Input

2010200


Output

YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a non-empty sequence of characters str, return true if sequence is Binary, else return false
Example 1:
Input:
str = 101
Output:
1
Explanation:
Since string contains only 0 and 1, output is 1.
Example 2:
Input:
str = 75
Output:
0
Explanation:
Since string contains digits other than 0 and 1, output is 0.
 
Your Task:
Complete the function isBinary() which takes an string str as input parameter and returns 1 if str is binary and returns 0 otherwise.
 
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <=T<= 50
1 <=Length of str<= 10000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Brain Network (medium)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Further research on zombie thought processes yielded interesting results. As we know from the previous problem, the nervous system of a zombie consists of *n* brains and *m* brain connectors joining some pairs of brains together. It was observed that the intellectual abilities of a zombie depend mainly on the topology of its nervous system. More precisely, we define the distance between two brains *u* and *v* (1<=≤<=*u*,<=*v*<=≤<=*n*) as the minimum number of brain connectors used when transmitting a thought between these two brains. The brain latency of a zombie is defined to be the maximum distance between any two of its brains. Researchers conjecture that the brain latency is the crucial parameter which determines how smart a given zombie is. Help them test this conjecture by writing a program to compute brain latencies of nervous systems.

In this problem you may assume that any nervous system given in the input is valid, i.e., it satisfies conditions (1) and (2) from the easy version.

Input Specification:
The first line of the input contains two space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100000) denoting the number of brains (which are conveniently numbered from 1 to *n*) and the number of brain connectors in the nervous system, respectively. In the next *m* lines, descriptions of brain connectors follow. Every connector is given as a pair of brains *a* *b* it connects (1<=≤<=*a*,<=*b*<=≤<=*n* and *a*<=≠<=*b*).

Output Specification:
Print one number – the brain latency.

Demo Input:
['4 3\n1 2\n1 3\n1 4\n', '5 4\n1 2\n2 3\n3 4\n3 5\n']

Demo Output:
['2', '3']

Note:
none

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

Write a program that calculates the number of grains of wheat on a chessboard given that the number on each square is double the previous one.

There are 64 squares on a chessboard.

#Example:
square(1) = 1
square(2) = 2
square(3) = 4
square(4) = 8
etc...

Write a program that shows how many grains were on each square

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Soon after the Chunga-Changa island was discovered, it started to acquire some forms of civilization and even market economy. A new currency arose, colloquially called "chizhik". One has to pay in chizhiks to buy a coconut now.

Sasha and Masha are about to buy some coconuts which are sold at price $z$ chizhiks per coconut. Sasha has $x$ chizhiks, Masha has $y$ chizhiks. Each girl will buy as many coconuts as she can using only her money. This way each girl will buy an integer non-negative number of coconuts.

The girls discussed their plans and found that the total number of coconuts they buy can increase (or decrease) if one of them gives several chizhiks to the other girl. The chizhiks can't be split in parts, so the girls can only exchange with integer number of chizhiks.

Consider the following example. Suppose Sasha has $5$ chizhiks, Masha has $4$ chizhiks, and the price for one coconut be $3$ chizhiks. If the girls don't exchange with chizhiks, they will buy $1 + 1 = 2$ coconuts. However, if, for example, Masha gives Sasha one chizhik, then Sasha will have $6$ chizhiks, Masha will have $3$ chizhiks, and the girls will buy $2 + 1 = 3$ coconuts. 

It is not that easy to live on the island now, so Sasha and Mash want to exchange with chizhiks in such a way that they will buy the maximum possible number of coconuts. Nobody wants to have a debt, so among all possible ways to buy the maximum possible number of coconuts find such a way that minimizes the number of chizhiks one girl gives to the other (it is not important who will be the person giving the chizhiks).


-----Input-----

The first line contains three integers $x$, $y$ and $z$ ($0 \le x, y \le 10^{18}$, $1 \le z \le 10^{18}$) — the number of chizhics Sasha has, the number of chizhics Masha has and the price of a coconut. 


-----Output-----

Print two integers: the maximum possible number of coconuts the girls can buy and the minimum number of chizhiks one girl has to give to the other.


-----Examples-----
Input
5 4 3

Output
3 1

Input
6 8 2

Output
7 0



-----Note-----

The first example is described in the statement. In the second example the optimal solution is to dot exchange any chizhiks. The girls will buy $3 + 4 = 7$ coconuts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's say string $s$ has period $k$ if $s_i = s_{i + k}$ for all $i$ from $1$ to $|s| - k$ ($|s|$ means length of string $s$) and $k$ is the minimum positive integer with this property.

Some examples of a period: for $s$="0101" the period is $k=2$, for $s$="0000" the period is $k=1$, for $s$="010" the period is $k=2$, for $s$="0011" the period is $k=4$.

You are given string $t$ consisting only of 0's and 1's and you need to find such string $s$ that:  String $s$ consists only of 0's and 1's;  The length of $s$ doesn't exceed $2 \cdot |t|$;  String $t$ is a subsequence of string $s$;  String $s$ has smallest possible period among all strings that meet conditions 1—3. 

Let us recall that $t$ is a subsequence of $s$ if $t$ can be derived from $s$ by deleting zero or more elements (any) without changing the order of the remaining elements. For example, $t$="011" is a subsequence of $s$="10101".


-----Input-----

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

Next $T$ lines contain test cases — one per line. Each line contains string $t$ ($1 \le |t| \le 100$) consisting only of 0's and 1's.


-----Output-----

Print one string for each test case — string $s$ you needed to find. If there are multiple solutions print any one of them.


-----Example-----
Input
4
00
01
111
110

Output
00
01
11111
1010


-----Note-----

In the first and second test cases, $s = t$ since it's already one of the optimal solutions. Answers have periods equal to $1$ and $2$, respectively.

In the third test case, there are shorter optimal solutions, but it's okay since we don't need to minimize the string $s$. String $s$ has period equal to $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given N,  reverse the digits of N.
 
Example 1:
Input: 200
Output: 2
Explanation: By reversing the digts of 
number, number will change into 2.
Example 2:
Input : 122
Output: 221
Explanation: By reversing the digits of 
number, number will change into 221.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function reverse_digit() which takes N as input parameter and returns the reversed number.
 
Expected Time Complexity: O(Log(N))
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 10^{15}

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