vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We have a grid with H rows and W columns of squares. We will represent the square at the i-th row from the top and j-th column from the left as (i,\ j). Also, we will define the distance between the squares (i_1,\ j_1) and (i_2,\ j_2) as |i_1 - i_2| + |j_1 - j_2|.

Snuke is painting each square in red, yellow, green or blue. Here, for a given positive integer d, he wants to satisfy the following condition:

* No two squares with distance exactly d have the same color.



Find a way to paint the squares satisfying the condition. It can be shown that a solution always exists.

Constraints

* 2 ≤ H, W ≤ 500
* 1 ≤ d ≤ H + W - 2

Input

Input is given from Standard Input in the following format:


H W d


Output

Print a way to paint the squares satisfying the condition, in the following format. If the square (i,\ j) is painted in red, yellow, green or blue, c_{ij} should be `R`, `Y`, `G` or `B`, respectively.


c_{11}c_{12}...c_{1W}
:
c_{H1}c_{H2}...c_{HW}

Output

Print a way to paint the squares satisfying the condition, in the following format. If the square (i,\ j) is painted in red, yellow, green or blue, c_{ij} should be `R`, `Y`, `G` or `B`, respectively.


c_{11}c_{12}...c_{1W}
:
c_{H1}c_{H2}...c_{HW}

Examples

Input

2 2 1


Output

RY
GR


Input

2 3 2


Output

RYB
RGB

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let s(x) be sum of digits in decimal representation of positive integer x. Given two integers n and m, find some positive integers a and b such that 

  * s(a) ≥ n, 
  * s(b) ≥ n, 
  * s(a + b) ≤ m. 

Input

The only line of input contain two integers n and m (1 ≤ n, m ≤ 1129).

Output

Print two lines, one for decimal representation of a and one for decimal representation of b. Both numbers must not contain leading zeros and must have length no more than 2230.

Examples

Input

6 5


Output

6 
7


Input

8 16


Output

35 
53

Note

In the first sample, we have n = 6 and m = 5. One valid solution is a = 6, b = 7. Indeed, we have s(a) = 6 ≥ n and s(b) = 7 ≥ n, and also s(a + b) = s(13) = 4 ≤ m.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mike wants to prepare for IMO but he doesn't know geometry, so his teacher gave him an interesting geometry problem. Let's define f([l, r]) = r - l + 1 to be the number of integer points in the segment [l, r] with l ≤ r (say that $f(\varnothing) = 0$). You are given two integers n and k and n closed intervals [l_{i}, r_{i}] on OX axis and you have to find: $\sum_{1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq n} f([ l_{i_{1}}, r_{i_{1}} ] \cap [ l_{i_{2}}, r_{i_{2}} ] \cap \ldots \cap [ l_{i_{k}}, r_{i_{k}} ])$ 

In other words, you should find the sum of the number of integer points in the intersection of any k of the segments. 

As the answer may be very large, output it modulo 1000000007 (10^9 + 7).

Mike can't solve this problem so he needs your help. You will help him, won't you? 


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 200 000) — the number of segments and the number of segments in intersection groups respectively.

Then n lines follow, the i-th line contains two integers l_{i}, r_{i} ( - 10^9 ≤ l_{i} ≤ r_{i} ≤ 10^9), describing i-th segment bounds.


-----Output-----

Print one integer number — the answer to Mike's problem modulo 1000000007 (10^9 + 7) in the only line.


-----Examples-----
Input
3 2
1 2
1 3
2 3

Output
5

Input
3 3
1 3
1 3
1 3

Output
3

Input
3 1
1 2
2 3
3 4

Output
6



-----Note-----

In the first example: 

$f([ 1,2 ] \cap [ 1,3 ]) = f([ 1,2 ]) = 2$;

$f([ 1,2 ] \cap [ 2,3 ]) = f([ 2,2 ]) = 1$;

$f([ 1,3 ] \cap [ 2,3 ]) = f([ 2,3 ]) = 2$.

So the answer is 2 + 1 + 2 = 5.

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


Each chemical element in its neutral state has a specific number of electrons associated with it. This is represented by the **atomic number** which is noted by an integer number next to or above each element of the periodic table (as highlighted in the image above).

As we move from left to right, starting from the top row of the periodic table, each element differs from its predecessor by 1 unit (electron). Electrons fill in different orbitals sets according to a specific order. Each set of orbitals, when full, contains an even number of electrons.

The orbital sets are:
* The _**s** orbital_ - a single orbital that can hold a maximum of 2 electrons.
* The _**p** orbital set_ - can hold 6 electrons.
* The _**d** orbital set_ - can hold 10 electrons.
* The _**f** orbital set_ - can hold 14 electrons.


The order in which electrons are filling the different set of orbitals is shown in the picture above. First electrons will occupy the **1s** orbital, then the **2s**, then the **2p** set, **3s** and so on.

Electron configurations show how the number of electrons of an element is distributed across each orbital set. Each orbital is written as a sequence that follows the order in the picture, joined by the number of electrons contained in that orbital set. The final electron configuration is a single string of orbital names and number of electrons per orbital set where the first 2 digits of each substring represent the orbital name followed by a number that states the number of electrons that the orbital set contains.

For example, a string that demonstrates an electron configuration of a chemical element that contains 10 electrons is: `1s2 2s2 2p6`. This configuration shows that there are two electrons in the `1s` orbital set, two electrons in the `2s` orbital set, and six electrons in the `2p` orbital set. `2 + 2 + 6 = 10` electrons total.

___

# Task

Your task is to write a function that displays the electron configuration built according to the Madelung rule of all chemical elements of the periodic table. The argument will be the symbol of a chemical element, as displayed in the periodic table.

**Note**: There will be a preloaded array called `ELEMENTS` with chemical elements sorted by their atomic number.

For example, when the element "O" is fed into the function the output should look like: 

`"O -> 1s2 2s2 2p4"`

However, there are some exceptions! The electron configurations of the elements below should end as:

```
Cr -> ...3d5 4s1
Cu -> ...3d10 4s1
Nb -> ...4d4 5s1
Mo -> ...4d5 5s1
Ru -> ...4d7 5s1
Rh -> ...4d8 5s1
Pd -> ...4d10 5s0
Ag -> ...4d10 5s1
La -> ...4f0 5d1
Ce -> ...4f1 5d1
Gd -> ...4f7 5d1 6s2
Pt -> ...4f14 5d9 6s1
Au -> ...4f14 5d10 6s1
Ac -> ...5f0 6d1 7s2
Th -> ...5f0 6d2 7s2
Pa -> ...5f2 6d1 7s2
U  -> ...5f3 6d1 7s2
Np -> ...5f4 6d1 7s2
Cm -> ...5f7 6d1 7s2
```

**Note**: for `Ni` the electron configuration should be `3d8 4s2` instead of `3d9 4s1`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Before the start of the football season in Berland a strange magic ritual is held. The most experienced magicians have to find a magic matrix of the size n × n (n is even number). Gods will never allow to start the championship without it. Matrix should contain integers from 0 to n - 1, main diagonal should contain only zeroes and matrix should be symmetric. Moreover, all numbers in each row should be different. Magicians are very tired of the thinking process, so they ask you to write a program to find such matrix.

Input

The first line contains one integer n (2 ≤ n ≤ 1000), n is even.

Output

Output n lines with n numbers each — the required matrix. Separate numbers with spaces. If there are several solutions, output any.

Examples

Input

2


Output

0 1
1 0


Input

4


Output

0 1 3 2
1 0 2 3
3 2 0 1
2 3 1 0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya calls a mask of a positive integer *n* the number that is obtained after successive writing of all lucky digits of number *n* from the left to the right. For example, the mask of number 72174994 is number 7744, the mask of 7 is 7, the mask of 9999047 is 47. Obviously, mask of any number is always a lucky number.

Petya has two numbers — an arbitrary integer *a* and a lucky number *b*. Help him find the minimum number *c* (*c*<=&gt;<=*a*) such that the mask of number *c* equals *b*.

Input Specification:
The only line contains two integers *a* and *b* (1<=≤<=*a*,<=*b*<=≤<=105). It is guaranteed that number *b* is lucky.

Output Specification:
In the only line print a single number — the number *c* that is sought by Petya.

Demo Input:
['1 7\n', '100 47\n']

Demo Output:
['7\n', '147\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a queue for the self-checkout tills at the supermarket. Your task is write a function to calculate the total time required for all the customers to check out!

### input
```if-not:c
* customers: an array of positive integers representing the queue. Each integer represents a customer, and its value is the amount of time they require to check out.
* n: a positive integer, the number of checkout tills.
```
```if:c
* customers: a pointer to an array of positive integers representing the queue. Each integer represents a customer, and its value is the amount of time they require to check out.
* customers_length: the length of the array that `customers` points to.
* n: a positive integer, the number of checkout tills.
```

### output
The function should return an integer, the total time required.

-------------------------------------------

## Important
**Please look at the examples and clarifications below, to ensure you understand the task correctly :)**

-------

### Examples

```python
queue_time([5,3,4], 1)
# should return 12
# because when n=1, the total time is just the sum of the times

queue_time([10,2,3,3], 2)
# should return 10
# because here n=2 and the 2nd, 3rd, and 4th people in the 
# queue finish before the 1st person has finished.

queue_time([2,3,10], 2)
# should return 12
```

### Clarifications

 * There is only ONE queue serving many tills, and
 * The order of the queue NEVER changes, and
 * The front person in the queue (i.e. the first element in the array/list) proceeds to a till as soon as it becomes free.

N.B. You should assume that all the test input will be valid, as specified above.

P.S. The situation in this kata can be likened to the more-computer-science-related idea of a thread pool, with relation to running multiple processes at the same time: https://en.wikipedia.org/wiki/Thread_pool

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
AtCoDeer the deer found N rectangle lying on the table, each with height 1.
If we consider the surface of the desk as a two-dimensional plane, the i-th rectangle i(1≤i≤N) covers the vertical range of [i-1,i] and the horizontal range of [l_i,r_i], as shown in the following figure:

AtCoDeer will move these rectangles horizontally so that all the rectangles are connected.
For each rectangle, the cost to move it horizontally by a distance of x, is x.
Find the minimum cost to achieve connectivity.
It can be proved that this value is always an integer under the constraints of the problem.

-----Constraints-----
 - All input values are integers.
 - 1≤N≤10^5
 - 1≤l_i<r_i≤10^9

-----Partial Score-----
 - 300 points will be awarded for passing the test set satisfying 1≤N≤400 and 1≤l_i<r_i≤400.

-----Input-----
The input is given from Standard Input in the following format:
N
l_1 r_1
l_2 r_2
:
l_N r_N

-----Output-----
Print the minimum cost to achieve connectivity.

-----Sample Input-----
3
1 3
5 7
1 3

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

The second rectangle should be moved to the left by a distance of 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To participate in a prize draw each one gives his/her firstname. 

Each letter of a firstname
has a value which is its rank in the English alphabet. `A` and `a` have rank `1`, `B` and `b` rank `2` and so on. 

The *length* of the firstname is added to the *sum* of these ranks hence a number `som`. 

An array of random weights is linked to the firstnames and each `som` is multiplied by 
its corresponding weight to get what they call a `winning number`.

Example:
```
names: "COLIN,AMANDBA,AMANDAB,CAROL,PauL,JOSEPH"
weights: [1, 4, 4, 5, 2, 1]

PauL -> som = length of firstname + 16 + 1 + 21 + 12 = 4 + 50 -> 54
The *weight* associated with PauL is 2 so PauL's *winning number* is 54 * 2 = 108.
```
Now one can sort the firstnames in decreasing order of the `winning numbers`. When two
people have the same `winning number` sort them *alphabetically* by their firstnames.

### Task:

- parameters: `st` a string of firstnames, `we` an array of weights, `n` a rank 

- return: the firstname of the participant whose rank is `n` 
(ranks are numbered from 1)

### Example:
```
names: "COLIN,AMANDBA,AMANDAB,CAROL,PauL,JOSEPH"
weights: [1, 4, 4, 5, 2, 1]
n: 4

The function should return: "PauL"
```
# Notes:
- The weight array is at least as long as the number of names, it can be longer.

- If `st` is empty return "No participants".

- If n is greater than the number of participants then return "Not enough participants".

- See Examples Test Cases for more examples.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Vasya and Football

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has started watching football games. He has learned that for some fouls the players receive yellow cards, and for some fouls they receive red cards. A player who receives the second yellow card automatically receives a red card.

Vasya is watching a recorded football match now and makes notes of all the fouls that he would give a card for. Help Vasya determine all the moments in time when players would be given red cards if Vasya were the judge. For each player, Vasya wants to know only the first moment of time when he would receive a red card from Vasya.

Input Specification:
The first line contains the name of the team playing at home. The second line contains the name of the team playing away. Both lines are not empty. The lengths of both lines do not exceed 20. Each line contains only of large English letters. The names of the teams are distinct.

Next follows number *n* (1<=≤<=*n*<=≤<=90) — the number of fouls. 

Each of the following *n* lines contains information about a foul in the following form: 
 -  first goes number *t* (1<=≤<=*t*<=≤<=90) — the minute when the foul occurs; -  then goes letter "h" or letter "a" — if the letter is "h", then the card was given to a home team player, otherwise the card was given to an away team player; -  then goes the player's number *m* (1<=≤<=*m*<=≤<=99); -  then goes letter "y" or letter "r" — if the letter is "y", that means that the yellow card was given, otherwise the red card was given. 
The players from different teams can have the same number. The players within one team have distinct numbers. The fouls go chronologically, no two fouls happened at the same minute.

Output Specification:
For each event when a player received his first red card in a chronological order print a string containing the following information:
 -  The name of the team to which the player belongs; -  the player's number in his team; -  the minute when he received the card. 
If no player received a card, then you do not need to print anything.

It is possible case that the program will not print anything to the output (if there were no red cards).

Demo Input:
['MC\nCSKA\n9\n28 a 3 y\n62 h 25 y\n66 h 42 y\n70 h 25 y\n77 a 4 y\n79 a 25 y\n82 h 42 r\n89 h 16 y\n90 a 13 r\n']

Demo Output:
['MC 25 70\nMC 42 82\nCSKA 13 90\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Leo has developed a new programming language C+=. In C+=, integer variables can only be changed with a "+=" operation that adds the right-hand side value to the left-hand side variable. For example, performing "a += b" when a = $2$, b = $3$ changes the value of a to $5$ (the value of b does not change).

In a prototype program Leo has two integer variables a and b, initialized with some positive values. He can perform any number of operations "a += b" or "b += a". Leo wants to test handling large integers, so he wants to make the value of either a or b strictly greater than a given value $n$. What is the smallest number of operations he has to perform?


-----Input-----

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

Each of the following $T$ lines describes a single test case, and contains three integers $a, b, n$ ($1 \leq a, b \leq n \leq 10^9$) — initial values of a and b, and the value one of the variables has to exceed, respectively.


-----Output-----

For each test case print a single integer — the smallest number of operations needed. Separate answers with line breaks.


-----Example-----
Input
2
1 2 3
5 4 100

Output
2
7



-----Note-----

In the first case we cannot make a variable exceed $3$ in one operation. One way of achieving this in two operations is to perform "b += a" twice.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the "Hobbit" movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.

There are n students in a summer school. Teachers chose exactly n pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym b to a student with name a as the length of the largest common prefix a and b. We will represent such value as $\operatorname{lcp}(a, b)$. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.

Find the matching between students and pseudonyms with the maximum quality.


-----Input-----

The first line contains number n (1 ≤ n ≤ 100 000) — the number of students in the summer school.

Next n lines contain the name of the students. Each name is a non-empty word consisting of lowercase English letters. Some names can be repeating.

The last n lines contain the given pseudonyms. Each pseudonym is a non-empty word consisting of small English letters. Some pseudonyms can be repeating.

The total length of all the names and pseudonyms doesn't exceed 800 000 characters.


-----Output-----

In the first line print the maximum possible quality of matching pseudonyms to students.

In the next n lines describe the optimal matching. Each line must have the form a b (1 ≤ a, b ≤ n), that means that the student who was number a in the input, must match to the pseudonym number b in the input.

The matching should be a one-to-one correspondence, that is, each student and each pseudonym should occur exactly once in your output. If there are several optimal answers, output any.


-----Examples-----
Input
5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel

Output
11
4 1
2 5
1 3
5 2
3 4



-----Note-----

The first test from the statement the match looks as follows:   bill  →  bilbo (lcp = 3)  galya  →  galadriel (lcp = 3)  gennady  →  gendalf (lcp = 3)  toshik  →  torin (lcp = 2)  boris  →  smaug (lcp = 0)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the easy version of the problem. The difference between the versions is that in the easy version all prices $a_i$ are different. You can make hacks if and only if you solved both versions of the problem.

Today is Sage's birthday, and she will go shopping to buy ice spheres. All $n$ ice spheres are placed in a row and they are numbered from $1$ to $n$ from left to right. Each ice sphere has a positive integer price. In this version all prices are different.

An ice sphere is cheap if it costs strictly less than two neighboring ice spheres: the nearest to the left and the nearest to the right. The leftmost and the rightmost ice spheres are not cheap. Sage will choose all cheap ice spheres and then buy only them.

You can visit the shop before Sage and reorder the ice spheres as you wish. Find out the maximum number of ice spheres that Sage can buy, and show how the ice spheres should be reordered.


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 10^5)$ — the number of ice spheres in the shop.

The second line contains $n$ different integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$ — the prices of ice spheres.


-----Output-----

In the first line print the maximum number of ice spheres that Sage can buy.

In the second line print the prices of ice spheres in the optimal order. If there are several correct answers, you can print any of them.


-----Example-----
Input
5
1 2 3 4 5

Output
2
3 1 4 2 5 


-----Note-----

In the example it's not possible to place ice spheres in any order so that Sage would buy $3$ of them. If the ice spheres are placed like this $(3, 1, 4, 2, 5)$, then Sage will buy two spheres: one for $1$ and one for $2$, because they are cheap.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dreamoon has just created a document of hard problems using notepad.exe. The document consists of n lines of text, ai denotes the length of the i-th line. He now wants to know what is the fastest way to move the cursor around because the document is really long.

Let (r, c) be a current cursor position, where r is row number and c is position of cursor in the row. We have 1 ≤ r ≤ n and 0 ≤ c ≤ ar.

We can use following six operations in notepad.exe to move our cursor assuming the current cursor position is at (r, c):

  1. up key: the new cursor position (nr, nc) = (max(r - 1, 1), min(anr, c))
  2. down key: the new cursor position (nr, nc) = (min(r + 1, n), min(anr, c))
  3. left key: the new cursor position (nr, nc) = (r, max(0, c - 1))
  4. right key: the new cursor position (nr, nc) = (r, min(anr, c + 1))
  5. HOME key: the new cursor position (nr, nc) = (r, 0)
  6. END key: the new cursor position (nr, nc) = (r, ar)



You're given the document description (n and sequence ai) and q queries from Dreamoon. Each query asks what minimal number of key presses is needed to move the cursor from (r1, c1) to (r2, c2).

Input

The first line contains an integer n(1 ≤ n ≤ 400, 000) — the number of lines of text. 

The second line contains n integers a1, a2, ..., an(1 ≤ ai ≤ 108).

The third line contains an integer q(1 ≤ q ≤ 400, 000). 

Each of the next q lines contains four integers r1, c1, r2, c2 representing a query (1 ≤ r1, r2 ≤ n, 0 ≤ c1 ≤ ar1, 0 ≤ c2 ≤ ar2).

Output

For each query print the result of the query.

Examples

Input

9
1 3 5 3 1 3 5 3 1
4
3 5 3 1
3 3 7 3
1 0 3 3
6 0 7 3


Output

2
5
3
2


Input

2
10 5
1
1 0 1 5


Output

3

Note

In the first sample, the first query can be solved with keys: HOME, right.

The second query can be solved with keys: down, down, down, END, down.

The third query can be solved with keys: down, END, down.

The fourth query can be solved with keys: END, down.

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