vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
-----Input-----

The input contains a single integer $a$ ($1 \le a \le 99$).


-----Output-----

Output "YES" or "NO".


-----Examples-----
Input
5

Output
YES

Input
13

Output
NO

Input
24

Output
NO

Input
46

Output
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Codeforces separates its users into $4$ divisions by their rating:

For Division 1: $1900 \leq \mathrm{rating}$

For Division 2: $1600 \leq \mathrm{rating} \leq 1899$

For Division 3: $1400 \leq \mathrm{rating} \leq 1599$

For Division 4: $\mathrm{rating} \leq 1399$

Given a $\mathrm{rating}$, print in which division the $\mathrm{rating}$ belongs.


-----Input-----

The first line of the input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of testcases.

The description of each test consists of one line containing one integer $\mathrm{rating}$ ($-5000 \leq \mathrm{rating} \leq 5000$).


-----Output-----

For each test case, output a single line containing the correct division in the format "Division X", where $X$ is an integer between $1$ and $4$ representing the division for the corresponding rating.


-----Examples-----

Input
7
-789
1299
1300
1399
1400
1679
2300
Output
Division 4
Division 4
Division 4
Division 4
Division 3
Division 2
Division 1


-----Note-----

For test cases $1-4$, the corresponding ratings are $-789$, $1299$, $1300$, $1399$, so all of them are in division $4$.

For the fifth test case, the corresponding rating is $1400$, so it is in division $3$.

For the sixth test case, the corresponding rating is $1679$, so it is in division $2$.

For the seventh test case, the corresponding rating is $2300$, so it is in division $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is `#` if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is `.` if that square is white.

We will repeatedly perform the following operation until all the squares are black:

* Every white square that shares a side with a black square, becomes black.



Find the number of operations that will be performed. The initial grid has at least one black square.

Constraints

* 1 \leq H,W \leq 1000
* A_{ij} is `#` or `.`.
* The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:


H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}


Output

Print the number of operations that will be performed.

Examples

Input

3 3
...
.#.
...


Output

2


Input

6 6
..#..#
......
..#..
......
.#....
....#.


Output

3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this exercise, you will have to create a function named tiyFizzBuzz. This function will take on a string parameter and will return that string with some characters replaced, depending on the value:

- If a letter is a upper case consonants, replace that character with "Iron".
- If a letter is a lower case consonants or a non-alpha character, do nothing to that character
- If a letter is a upper case vowel, replace that character with "Iron Yard".
- If a letter is a lower case vowel, replace that character with "Yard".

Ready?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your car starts at position 0 and speed +1 on an infinite number line.  (Your car can go into negative positions.)
Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).
When you get an instruction "A", your car does the following: position += speed, speed *= 2.
When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1.  (Your position stays the same.)
For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.
Now for some target position, say the length of the shortest sequence of instructions to get there.
Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.

Example 2:
Input: 
target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.

 
Note: 

1 <= target <= 10000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Inna and Sweet Matrix

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Inna loves sweets very much. That's why she decided to play a game called "Sweet Matrix".

Inna sees an *n*<=×<=*m* matrix and *k* candies. We'll index the matrix rows from 1 to *n* and the matrix columns from 1 to *m*. We'll represent the cell in the *i*-th row and *j*-th column as (*i*,<=*j*). Two cells (*i*,<=*j*) and (*p*,<=*q*) of the matrix are adjacent if |*i*<=-<=*p*|<=+<=|*j*<=-<=*q*|<==<=1. A path is a sequence of the matrix cells where each pair of neighbouring cells in the sequence is adjacent. We'll call the number of cells in the sequence the path's length.

Each cell of the matrix can have at most one candy. Initiallly, all the cells are empty. Inna is trying to place each of the *k* candies in the matrix one by one. For each candy Inna chooses cell (*i*,<=*j*) that will contains the candy, and also chooses the path that starts in cell (1,<=1) and ends in cell (*i*,<=*j*) and doesn't contain any candies. After that Inna moves the candy along the path from cell (1,<=1) to cell (*i*,<=*j*), where the candy stays forever. If at some moment Inna can't choose a path for the candy, she loses. If Inna can place all the candies in the matrix in the described manner, then her penalty equals the sum of lengths of all the paths she has used.

Help Inna to minimize the penalty in the game.

Input Specification:
The first line of the input contains three integers *n*, *m* and *k* (1<=≤<=*n*,<=*m*<=≤<=50,<=1<=≤<=*k*<=≤<=*n*·*m*).

Output Specification:
In the first line print an integer — Inna's minimum penalty in the game.

In the next *k* lines print the description of the path for each candy. The description of the path of the candy that is placed *i*-th should follow on the *i*-th line. The description of a path is a sequence of cells. Each cell must be written in the format (*i*,<=*j*), where *i* is the number of the row and *j* is the number of the column. You are allowed to print extra whitespaces in the line. If there are multiple optimal solutions, print any of them.

Please follow the output format strictly! If your program passes the first pretest, then the output format is correct.

Demo Input:
['4 4 4\n']

Demo Output:
['8\n(1,1) (2,1) (2,2)\n(1,1) (1,2)\n(1,1) (2,1)\n(1,1)\n']

Note:
Note to the sample. Initially the matrix is empty. Then Inna follows her first path, the path penalty equals the number of cells in it — 3. Note that now no path can go through cell (2, 2), as it now contains a candy. The next two candies go to cells (1, 2) and (2, 1). Inna simply leaves the last candy at cell (1, 1), the path contains only this cell. The total penalty is: 3 + 2 + 2 + 1 = 8.

Note that Inna couldn't use cell (1, 1) to place, for instance, the third candy as in this case she couldn't have made the path for the fourth candy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Monocarp got a job. His working day lasts exactly $m$ minutes. During work, Monocarp wants to drink coffee at certain moments: there are $n$ minutes $a_1, a_2, \dots, a_n$, when he is able and willing to take a coffee break (for the sake of simplicity let's consider that each coffee break lasts exactly one minute). 

However, Monocarp's boss doesn't like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute $a_i$, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least $d$ minutes pass between any two coffee breaks. Monocarp also wants to take these $n$ coffee breaks in a minimum possible number of working days (he doesn't count days when he is not at work, and he doesn't take coffee breaks on such days). Take into account that more than $d$ minutes pass between the end of any working day and the start of the following working day.

For each of the $n$ given minutes determine the day, during which Monocarp should take a coffee break in this minute. You have to minimize the number of days spent. 


-----Input-----

The first line contains three integers $n$, $m$, $d$ $(1 \le n \le 2\cdot10^{5}, n \le m \le 10^{9}, 1 \le d \le m)$ — the number of coffee breaks Monocarp wants to have, the length of each working day, and the minimum number of minutes between any two consecutive coffee breaks.

The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le m)$, where $a_i$ is some minute when Monocarp wants to have a coffee break.


-----Output-----

In the first line, write the minimum number of days required to make a coffee break in each of the $n$ given minutes. 

In the second line, print $n$ space separated integers. The $i$-th of integers should be the index of the day during which Monocarp should have a coffee break at minute $a_i$. Days are numbered from $1$. If there are multiple optimal solutions, you may print any of them.


-----Examples-----
Input
4 5 3
3 5 1 2

Output
3
3 1 1 2 

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

Output
2
2 1 1 2 2 1 2 1 1 2 



-----Note-----

In the first example, Monocarp can take two coffee breaks during the first day (during minutes $1$ and $5$, $3$ minutes will pass between these breaks). One break during the second day (at minute $2$), and one break during the third day (at minute $3$).

In the second example, Monocarp can determine the day of the break as follows: if the minute when he wants to take a break is odd, then this break is on the first day, if it is even, then this break is on the second day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N: Mail order

Mr. Komozawa bought building blocks toys from Makai mail order.

The building blocks are in the shape of a cube with a side length of 1, and are stacked on squares divided into $ H $ pieces vertically and $ W $ pieces horizontally.

Seen from the side, $ A_1, A_2, A_3, \ dots, A_H $ blocks were stacked in order from the left.

When viewed from the front, $ B_1, B_2, B_3, \ dots, B_W $ blocks were stacked in order from the left.

Mr. Komozawa is great, so I decided to guess the total number of blocks from this information alone.

If you answer a small number and make a mistake, it will be awkward, so I would like to answer the maximum number that can be considered.

input

The first line is given the integers $ H, W $, separated by blanks.

On the second line, $ H $ integers $ A_1, A_2, A_3, \ dots, A_H $ representing the figure when viewed from the side are given, separated by blanks.

On the third line, $ W $ integers $ B_1, B_2, B_3, \ dots, B_W $ representing the front view are given, separated by blanks.

output

Output the maximum number of blocks that can be considered from this information.

Constraint

* $ H, W $ are integers greater than or equal to $ 1 $ and less than or equal to $ 100 \ 000 $
* $ A_1, A_2, A_3, \ dots, A_H $ are integers greater than or equal to $ 1 $ and less than or equal to $ 100 \ 000 \ 000 $
* $ B_1, B_2, B_3, \ dots, B_W $ are integers greater than or equal to $ 1 $ and less than or equal to $ 100 \ 000 \ 000 $
* It is guaranteed that there is a stacking method of blocks that meets the conditions for all inputs.



Input example 1


twenty two
1 5
1 5


Output example 1


8


Let's represent the $ X $ th cell in the vertical direction and the $ Y $ th cell in the horizontal direction by $ (X, Y) $.

A total of $ 8 $ if 5 pieces are stacked on the mass $ (2, 2) $ and $ 1 $ is stacked on the mass $ (1, 1) $, $ (1, 2) $, $ (2, 1) $. Blocks will be piled up.

The answer is $ 8 $, as it is unlikely that you have more than $ 9 $.

Input example 2


3 3
2 4 5
3 1 5


Output example 2


twenty two






Example

Input

2 2
1 5
1 5


Output

8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sometimes, I want to quickly be able to convert miles per imperial gallon into kilometers per liter.

Create an application that will display the number of kilometers per liter (output) based on the number of miles per imperial gallon (input).

Make sure to round off the result to two decimal points. If the answer ends with a 0, it should be rounded off without the 0. So instead of 5.50, we should get 5.5.

Some useful associations relevant to this kata:
1 Imperial Gallon = 4.54609188 litres
1 Mile = 1.609344 kilometres

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string t, we will call it unbalanced if and only if the length of t is at least 2, and more than half of the letters in t are the same. For example, both voodoo and melee are unbalanced, while neither noon nor a is.
You are given a string s consisting of lowercase letters. Determine if there exists a (contiguous) substring of s that is unbalanced. If the answer is positive, show a position where such a substring occurs in s.

-----Constraints-----
 - 2 ≦ |s| ≦ 10^5
 - s consists of lowercase letters.

-----Partial Score-----
 - 200 points will be awarded for passing the test set satisfying 2 ≦ N ≦ 100.

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

-----Output-----
If there exists no unbalanced substring of s, print -1 -1.
If there exists an unbalanced substring of s, let one such substring be s_a s_{a+1} ... s_{b} (1 ≦ a < b ≦ |s|), and print a b. If there exists more than one such substring, any of them will be accepted.

-----Sample Input-----
needed

-----Sample Output-----
2 5

The string s_2 s_3 s_4 s_5 = eede is unbalanced. There are also other unbalanced substrings. For example, the output 2 6 will also be accepted.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Rubik is very keen on number permutations. 

A permutation *a* with length *n* is a sequence, consisting of *n* different numbers from 1 to *n*. Element number *i* (1<=≤<=*i*<=≤<=*n*) of this permutation will be denoted as *a**i*.

Furik decided to make a present to Rubik and came up with a new problem on permutations. Furik tells Rubik two number permutations: permutation *a* with length *n* and permutation *b* with length *m*. Rubik must give an answer to the problem: how many distinct integers *d* exist, such that sequence *c* (*c*1<==<=*a*1<=+<=*d*,<=*c*2<==<=*a*2<=+<=*d*,<=...,<=*c**n*<==<=*a**n*<=+<=*d*) of length *n* is a subsequence of *b*.

Sequence *a* is a subsequence of sequence *b*, if there are such indices *i*1,<=*i*2,<=...,<=*i**n* (1<=≤<=*i*1<=&lt;<=*i*2<=&lt;<=...<=&lt;<=*i**n*<=≤<=*m*), that *a*1<==<=*b**i*1, *a*2<==<=*b**i*2, ..., *a**n*<==<=*b**i**n*, where *n* is the length of sequence *a*, and *m* is the length of sequence *b*. 

You are given permutations *a* and *b*, help Rubik solve the given problem.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=*m*<=≤<=200000) — the sizes of the given permutations. The second line contains *n* distinct integers — permutation *a*, the third line contains *m* distinct integers — permutation *b*. Numbers on the lines are separated by spaces.

Output Specification:
On a single line print the answer to the problem.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Young Sheldon is given the task to teach Chemistry to his brother Georgie. After teaching him how to find total atomic weight, Sheldon gives him some formulas which consist of $x$, $y$ and $z$ atoms as an assignment. 
You already know that Georgie doesn't like Chemistry, so he want you to help him solve this assignment.
Let the chemical formula be given by the string $S$. It consists of any combination of x, y and z with some value associated with it as well as parenthesis to encapsulate any combination. Moreover, the atomic weight of x, y and z are 2, 4 and 10 respectively.
You are supposed to find the total atomic weight of the element represented by the given formula.
For example, for the formula $(x_2y_2)_3z$, given string $S$ will be: $(x2y2)3z$. Hence, substituting values of x, y and z, total atomic weight will be 
$(2*2+4*2)*3 + 10 = 46$.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input $S$. 

-----Output:-----
For each testcase, output in a single line, the total atomic weight.

-----Constraints-----
- $1 \leq T \leq 100$
- Length of string $S \leq 100$
- String contains $x, y, z, 1, 2,..., 9$ and parenthesis

-----Sample Input:-----
2
(xy)2
x(x2y)3(z)2

-----Sample Output:-----
12
46

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N cards placed on a grid with H rows and W columns of squares.

The i-th card has an integer A_i written on it, and it is placed on the square at the R_i-th row from the top and the C_i-th column from the left.

Multiple cards may be placed on the same square.

You will first pick up at most one card from each row.

Then, you will pick up at most one card from each column.

Find the maximum possible sum of the integers written on the picked cards.

Constraints

* All values are integers.
* 1 \leq N \leq 10^5
* 1 \leq H, W \leq 10^5
* 1 \leq A_i \leq 10^5
* 1 \leq R_i \leq H
* 1 \leq C_i \leq W

Input

Input is given from Standard Input in the following format:


N H W
R_1 C_1 A_1
R_2 C_2 A_2
\vdots
R_N C_N A_N


Output

Print the maximum possible sum of the integers written on the picked cards.

Examples

Input

6 2 2
2 2 2
1 1 8
1 1 5
1 2 9
1 2 7
2 1 4


Output

28


Input

13 5 6
1 3 35902
4 6 19698
4 6 73389
3 6 3031
3 1 4771
1 4 4784
2 1 36357
2 1 24830
5 6 50219
4 6 22645
1 2 30739
1 4 68417
1 5 78537


Output

430590


Input

1 100000 100000
1 1 1


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
With the T20 world cup going on, a list of batsmen was prepared with their country code and their T20I career runs.  
The list contains data of N batsmen (country-code and runs).  
Number of countries may range from 1 to N and each country has its unique code.  
The list is pretty unorganized. Virat and Maxwell do not like it. They decided to group all the players belonging to same country together. 

 Virat likes arranging stuffs in ascending order and wants the data list to be sorted in ascending order, while Maxwell prefers descending order.

 As they are good friends, they mutually agreed that country codes should be sorted in ascending order and for each country code, the runs of all the batsmen for that particular country should be sorted in descending order. 

As the mighty clash between Australia and India is going to start shortly, Virat and Maxwell don't have the time to organize the list. Can you help them to sort the list, the way they want?
(See test cases for clarification)
INPUT:
First line contains a integer N, the number of Batsmen.
 Next N lines, contains two integers separated by space, country-code and runs of the ith batsmen . (1 ≤ i ≤ N)

OUTPUT :
 Print N lines containing two integers, i.e. country-code and runs of the batsmen, sorted in the order Virat and Maxwell wants.
CONSTRAINS

1 ≤ N ≤ 1000006
0 ≤ Runs ≤ 10^9

Disclaimer : All country-codes and runs are fictional and has no relation and significance with real life.

SAMPLE INPUT
5
4 12
2 1
3 10
2 7
2 5

SAMPLE OUTPUT
2 7
2 5
2 1
3 10
4 12

Explanation

Country '4' has one player with runs '12',  
Country '3' has one player with run '10', 
Country '2' has three players with runs '1' , '7' and '5' .
Countries are sorted in increasing order 2 -> 2 -> 2 -> 3 -> 4.
The players for each country should have runs in descending order, so final output is 
(2,7) (2,5), (2,1) , (3,10), (4,12).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ember and Storm play a game. First, Ember picks a labelled tree T of n vertices, such that the degree of every vertex is at most d. Then, Storm picks two distinct vertices u and v in this tree and writes down the labels of the vertices in the path from u to v in a sequence a1, a2... ak. Finally, Ember picks any index i (1 ≤ i < k) in the array. Now he performs one of the following two operations exactly once:

  * flip the subrange [i + 1, k] and add ai to it. After this, the sequence becomes a1, ... ai, ak + ai, ak - 1 + ai, ... ai + 1 + ai
  * negate the subrange [i + 1, k] and add ai to it. i.e., the array becomes a1, ... ai, - ai + 1 + ai, - ai + 2 + ai, ... - ak + ai



Ember wins if the array is monotonically increasing or decreasing after this. Otherwise Storm wins.

The game can be described by the tuple (T, u, v, i, op) where op is «flip» or «negate» depending on the action Ember chose in the last turn. Find the number of tuples that can occur if Ember and Storm play optimally. When they play optimally, if there are multiple moves by which they are guaranteed to win, then they may play any of the winning moves. Otherwise, if someone loses no matter what they play, then they may play any of the possible moves.

Report the answer modulo m.

Input

The input consists of a single line containing three integers n, d and m (2 ≤ n ≤ 200, 1 ≤ d < n, 1 ≤ m ≤ 2·109).

Output

Print a single number — the number of possible tuples if Ember and Storm play as described, modulo m.

Examples

Input

2 1 1000000007


Output

4


Input

3 1 250


Output

0


Input

3 2 100


Output

36

Note

In the first sample case, there is only one possible tree. There are two possible paths, 1 to 2 and 2 to 1. For both paths, i can only be 1, and op can take both possibilities. Therefore, the answer is 4.

In the second sample, there are no possible trees.

In the third sample, there are three possible trees.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers, sort the array according to frequency of elements. That is elements that have higher frequency come first. If frequencies of two elements are same, then smaller number comes first.
Example 1:
Input:
N = 5
A[] = {5,5,4,6,4}
Output: 4 4 5 5 6
Explanation: The highest frequency here is
2. Both 5 and 4 have that frequency. Now
since the frequencies are same then 
smallerelement comes first. So 4 4 comes 
firstthen comes 5 5. Finally comes 6.
The output is 4 4 5 5 6.
Example 2:
Input:
N = 5
A[] = {9,9,9,2,5}
Output: 9 9 9 2 5
Explanation: The highest frequency here is
3. The element 9 has the highest frequency
So 9 9 9 comes first. Now both 2 and 5
have same frequency. So we print smaller
element first.
The output is 9 9 9 2 5.
Your Task:
You only need to complete the function sortByFreq that takes arr, and n as parameters and returns the sorted array.
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(N). 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{5}

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