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

Digital Cypher assigns to each letter of the alphabet unique number. For example:

```
 a  b  c  d  e  f  g  h  i  j  k  l  m
 1  2  3  4  5  6  7  8  9 10 11 12 13
 n  o  p  q  r  s  t  u  v  w  x  y  z
14 15 16 17 18 19 20 21 22 23 24 25 26
```

Instead of letters in encrypted word we write the corresponding number, eg. The word scout:

```
 s  c  o  u  t
19  3 15 21 20
```
Then we add to each obtained digit consecutive digits from the key. For example. In case of key equal to `1939` :

```
   s  c  o  u  t
  19  3 15 21 20
 + 1  9  3  9  1
 ---------------
  20 12 18 30 21
  
   m  a  s  t  e  r  p  i  e  c  e
  13  1 19 20  5 18 16  9  5  3  5
+  1  9  3  9  1  9  3  9  1  9  3
  --------------------------------
  14 10 22 29  6 27 19 18  6  12 8
```

# Task

Write a function that accepts `str` string and `key` number and returns an array of integers representing encoded `str`.

# Input / Output

The `str` input string consists of lowercase characters only.
The `key` input number is a positive integer.

# Example

```
Encode("scout",1939);  ==>  [ 20, 12, 18, 30, 21]
Encode("masterpiece",1939);  ==>  [ 14, 10, 22, 29, 6, 27, 19, 18, 6, 12, 8]
```

# Digital cypher series
- [Digital cypher vol 1](https://www.codewars.com/kata/592e830e043b99888600002d)
- [Digital cypher vol 2](https://www.codewars.com/kata/592edfda5be407b9640000b2)
- [Digital cypher vol 3 - missing key](https://www.codewars.com/kata/5930d8a4b8c2d9e11500002a)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese and Russian as well. 

	Mike is given an undirected graph G of N vertices and M edges. A non-negative integer X_{i} is assigned to the i'th vertex of G, for 1 ≤ i ≤ N.

	Mike was asked to assign labels to each edge of the graph so that the following condition is satisfied:

	Let's suppose that the j'th edge of G connects vertices U_{j} and V_{j}. Then, a non-negative integer Y_{j} equals to XU_{j} xor XV_{j}.

	This challenge was too easy for Mike and he solved it quickly.

	The next day, Mike started to worry that he had solved the problem too quickly and had made a lot of mistakes, so he decided to double-check his answers. To his horror, Mike discovered that all the values of X_{i} had been lost!

	Mike is a very meticulous person and he doesn't like making mistakes, so he decided to create his own values of X_{i} that still produce the same values of Y_{j}.

	Your task is to determine whether it is possible to do so. If it is, you should output the K'th lexicographically valid sequence (X_{1}, X_{2}, ..., X_{N}) that satisfies the above conditions, knowing the structure of G and all the values Y_{j}.

------ Note ------ 

	Maybe some of you aren't familiar with some terms in the statement. Here are some articles that could help you understand the problem correctly:

XOR operation: http://en.wikipedia.org/wiki/Exclusive_{or}

	Also, the stack memory size is quite limited on CodeChef, so a deep recursion may lead to the Runtime Error verdict.

------ Input ------ 

	The first line of the input contains the integers N, M and K.

	The next M lines describe the edges of G; the j'th line contains three integers U_{j}, V_{j} and Y_{j}.

	It's guaranteed that G doesn't contain multiple edges and loops.

------ Output ------ 

	If there is no valid labelling, or less than K valid labellings, the only line of the output should contain -1. Otherwise, the only line of the output should contain N non-negative integers, denoting the K'th lexicographically valid sequence (X_{1}, X_{2}, ..., X_{N}).

	It's guaranteed that in the correct sequence all of the values of X_{i} won't exceed the 32-bit signed integer limit.

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

1 ≤ N ≤ 200,000(2 × 10^{5});
0 ≤ M ≤ 300,000(3 × 10^{5});
1 ≤ K ≤ 1,000,000,000(10^{9});
1 ≤ U_{j} ≠ V_{j} ≤ N;
0 ≤ Y_{j} < 2^{31}.

------ Example ------ 

Input:
5 4 2
1 2 5
1 3 9
2 4 0
2 5 1

Output:
1 4 8 4 5 

------ Explanation ------ 

	The first lexicographically valid sequence is equal to (0, 5, 9, 5, 4);

	The second lexicographically valid sequence is equal to (1, 4, 8, 4, 5) - that's the one that should be printed out as the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose that you are in a campus and have to go for classes day by day. As you may see, when you hurry to a classroom, you surprisingly find that many seats there are already occupied. Today you and your friends went for class, and found out that some of the seats were occupied.

The classroom contains $n$ rows of seats and there are $m$ seats in each row. Then the classroom can be represented as an $n \times m$ matrix. The character '.' represents an empty seat, while '*' means that the seat is occupied. You need to find $k$ consecutive empty seats in the same row or column and arrange those seats for you and your friends. Your task is to find the number of ways to arrange the seats. Two ways are considered different if sets of places that students occupy differs.


-----Input-----

The first line contains three positive integers $n,m,k$ ($1 \leq n, m, k \leq 2\,000$), where $n,m$ represent the sizes of the classroom and $k$ is the number of consecutive seats you need to find.

Each of the next $n$ lines contains $m$ characters '.' or '*'. They form a matrix representing the classroom, '.' denotes an empty seat, and '*' denotes an occupied seat.


-----Output-----

A single number, denoting the number of ways to find $k$ empty seats in the same row or column.


-----Examples-----
Input
2 3 2
**.
...

Output
3

Input
1 2 2
..

Output
1

Input
3 3 4
.*.
*.*
.*.

Output
0



-----Note-----

In the first sample, there are three ways to arrange those seats. You can take the following seats for your arrangement.   $(1,3)$, $(2,3)$  $(2,2)$, $(2,3)$  $(2,1)$, $(2,2)$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A robot is standing at the origin of the infinite two-dimensional plane. Each second the robot moves exactly $1$ meter in one of the four cardinal directions: north, south, west, and east. For the first step the robot can choose any of the four directions, but then at the end of every second it has to turn 90 degrees left or right with respect to the direction it just moved in. For example, if the robot has just moved north or south, the next step it takes has to be either west or east, and vice versa.

The robot makes exactly $n$ steps from its starting position according to the rules above. How many different points can the robot arrive to at the end? The final orientation of the robot can be ignored.


-----Input-----

The only line contains a single integer $n$ ($1 \leq n \leq 1000$) — the number of steps the robot makes.


-----Output-----

Print a single integer — the number of different possible locations after exactly $n$ steps.


-----Examples-----

Input
1
Output
4
Input
2
Output
4
Input
3
Output
12


-----Note-----

In the first sample case, the robot will end up 1 meter north, south, west, or east depending on its initial direction.

In the second sample case, the robot will always end up $\sqrt{2}$ meters north-west, north-east, south-west, or south-east.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An array of integers $p_{1},p_{2}, \ldots,p_{n}$ is called a permutation if it contains each number from $1$ to $n$ exactly once. For example, the following arrays are permutations: $[3,1,2], [1], [1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2], [1,1], [2,3,4]$.

There is a hidden permutation of length $n$.

For each index $i$, you are given $s_{i}$, which equals to the sum of all $p_{j}$ such that $j < i$ and $p_{j} < p_{i}$. In other words, $s_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.

Your task is to restore the permutation.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{5}$) — the size of the permutation.

The second line contains $n$ integers $s_{1}, s_{2}, \ldots, s_{n}$ ($0 \le s_{i} \le \frac{n(n-1)}{2}$).

It is guaranteed that the array $s$ corresponds to a valid permutation of length $n$.


-----Output-----

Print $n$ integers $p_{1}, p_{2}, \ldots, p_{n}$ — the elements of the restored permutation. We can show that the answer is always unique.


-----Examples-----
Input
3
0 0 0

Output
3 2 1

Input
2
0 1

Output
1 2

Input
5
0 1 1 1 10

Output
1 4 3 2 5



-----Note-----

In the first example for each $i$ there is no index $j$ satisfying both conditions, hence $s_i$ are always $0$.

In the second example for $i = 2$ it happens that $j = 1$ satisfies the conditions, so $s_2 = p_1$.

In the third example for $i = 2, 3, 4$ only $j = 1$ satisfies the conditions, so $s_2 = s_3 = s_4 = 1$. For $i = 5$ all $j = 1, 2, 3, 4$ are possible, so $s_5 = p_1 + p_2 + p_3 + p_4 = 10$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Caesar cipher is one of the simplest encryption techniques. To transform the original message into encrypted one using key k, one has to replace each letter with a letter which is k positions later in the alphabet (if this takes the position beyond Z, the rest of it is counted from the start of the alphabet). In a more formal way, if letters of the alphabet are enumerated starting with 0, the result of encryption for character x will be <image> (26 is the number of letters in the Latin alphabet).

You are given the original message and the encryption key k. Output the resulting cipher.

Input

The first line of input contains the original message — a sequence uppercase Latin letters («A»-«Z»). The length of the message is from 1 to 10, inclusive.

The second line contains an integer k (0 ≤ k ≤ 25).

Output

Output the result of encryption.

Examples

Input

CODEFORCES
5


Output

HTIJKTWHJX


Input

WIXYZILWYM
6


Output

CODEFORCES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tomorrow Peter has a Biology exam. He does not like this subject much, but d days ago he learnt that he would have to take this exam. Peter's strict parents made him prepare for the exam immediately, for this purpose he has to study not less than minTimei and not more than maxTimei hours per each i-th day. Moreover, they warned Peter that a day before the exam they would check how he has followed their instructions.

So, today is the day when Peter's parents ask him to show the timetable of his preparatory studies. But the boy has counted only the sum of hours sumTime spent him on preparation, and now he wants to know if he can show his parents a timetable sсhedule with d numbers, where each number sсhedulei stands for the time in hours spent by Peter each i-th day on biology studies, and satisfying the limitations imposed by his parents, and at the same time the sum total of all schedulei should equal to sumTime.

Input

The first input line contains two integer numbers d, sumTime (1 ≤ d ≤ 30, 0 ≤ sumTime ≤ 240) — the amount of days, during which Peter studied, and the total amount of hours, spent on preparation. Each of the following d lines contains two integer numbers minTimei, maxTimei (0 ≤ minTimei ≤ maxTimei ≤ 8), separated by a space — minimum and maximum amount of hours that Peter could spent in the i-th day.

Output

In the first line print YES, and in the second line print d numbers (separated by a space), each of the numbers — amount of hours, spent by Peter on preparation in the corresponding day, if he followed his parents' instructions; or print NO in the unique line. If there are many solutions, print any of them.

Examples

Input

1 48
5 7


Output

NO


Input

2 5
0 1
3 5


Output

YES
1 4 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a binary string S. You can perform the following operation on S:
Select any substring S_{L \dots R} (1 ≤ L ≤ R ≤ |S|) which is sorted in non-decreasing order and remove it from S.
(Both the left and right halves are concatenated after performing the operation)

For e.g. if S = 100011000, we can perform the following operation: 100\underline{011}000 \rightarrow 100000

Find the minimum number of operations required so that the final binary string S is sorted in non-decreasing order.

Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the length of the binary string S.
- The second line of each test case contains a binary string S of length N containing 0s and 1s only.

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

For each test case, output the minimum number of operations required so that the final binary string S is sorted in non-decreasing order.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$S$ contains $0$ and $1$ only.
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
000
5
01110
2
10

----- Sample Output 1 ------ 
0
1
1

----- explanation 1 ------ 
Test case $1$: The binary string is already sorted, so we need no operations.

Test case $2$: We can use one operation to remove the sorted substring $S_{2 \dots 4} = 111$. Thus, the remaining string $00$ is sorted.

Test case $3$: We can use one operation to remove the sorted substring $S_{2 \dots 2} = 0$. Thus, the remaining string $1$ is sorted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string is made of only lowercase latin letters (a,b,c,d,.....,z). Can you find the length of the lexicographically smallest string such that it has exactly ${K}$ sub-strings, each of which are palindromes? 

Input Format

The first line of input contains single integer ${T}$ - the number of testcases. 

T lines follow, each containing the integer ${K}$.

Constraints

$1\leq T\leq100$  
$1\leq K\leq10^{12}$  

Output Format

Output exactly ${T}$ lines. Each line should contain single integer - the length of the lexicographically smallest string.

Sample Input
2
10
17

Sample Output
4
7

Explanation

for $K=10$, one of the smallest possible strings that satisfies the property is aaaa. 
All $10$ palindromes are 

a,a,a,a 
aa, aa, aa
aaa, aaa
aaaa

Note

Two sub-strings with different indices are both counted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An alphabetical string is a string consisting of $0$ or more capital letters (i.e. [‘A’..‘Z’]). Given an alphabetical string $S[1..N]$, determine the number of palindromic alphabetical strings of length $2N$ that contains $S$ as a subsequence (not necessarily contiguous). A string is palindromic if it is equal to its reverse.

-----Input-----
The first line of input is an integer representing $N$, constrained to $0 \leq N \leq 200$.

The second line of input is an alphabetical string $S$ of length $N$.

-----Output-----
Output the number of palindromic alphabetical strings of length $2N$ containing $S$ as a subsequence. As this could be rather large, output it modulo $10^9+7$.

-----Examples-----
Sample Input:
2
AA
Sample Output:
51

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Due to the COVID pandemic, there has been an increase in the number of cases if a hospital. The management has decided to clear a large square area for the patients and arrange for beds. But the beds can't be too near to each other.
The area is of dimension $N$ x $N$
The whole area is already divided into blocks. $1$ means there's a bed in the block, $0$ denotes there isn't. Note, beds placed on consecutive diagonal blocks are safe.
This is a SAFE example:
1 0
0 1
This is an UNSAFE example:
0 1 1
0 0 0
1 0 0
To avoid spreading the virus even further, you have to make sure no two adjacent blocks have beds in them. This is done to maintain distance between beds.
Return an output of "SAFE" if you find the workers have arranged the beds with due consideration to the distance needed. Return "UNSAFE" otherwise.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Next line contains $N$.
- Next $N$ lines will contain $N$ number of space-separated integers $Ai$ which make denote the beds in the area.

-----Output:-----
For each test case, output in a single line whether the total arrangement is "SAFE" or "UNSAFE". Even if there's a single unsafe bed in the whole area, report the whole area as "UNSAFE".

-----Constraints-----
- $1 \leq T \leq 100$
- $0 \leq Ai \leq 1$
- $2 \leq N \leq 100$

-----Subtasks-----
- 30 points : $1 \leq N \leq 7$
- 70 points : Original constraints

-----Sample Input:-----
2
4
1 0 1 0
0 0 0 1
0 1 0 0
1 0 0 1
4
1 0 1 0
0 0 0 0
1 0 1 1
0 1 0 0

-----Sample Output:-----
SAFE
UNSAFE

-----EXPLANATION:-----
Beds placed on blocks diagonally are not a problem.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 John is new to spreadsheets. He is well aware of rows and columns, but he is not comfortable with spreadsheets numbering system.
```
Spreadsheet             Row Column
A1                      R1C1
D5                       R5C4
AA48                    R48C27
BK12                   R12C63```
Since John has a lot of work to do both in row-column and spreadsheet systems, he needs a program that converts cell numbers from one system to another.


# Example

 For `s = "A1"`, the result should be `"R1C1"`.

 For `s = "R48C27"`, the result should be `"AA48"`.
 
- Input/Output


 - `[input]` string `s`

  The position (in spreadsheet or row-column numbering system).

  `Spreadsheet : A1 to CRXO65535`
  
  `Row-Column: R1C1 to R65535C65535`
  
  
 - `[output]` a string

  The position (in the opposite format; if input was in spreadsheet system, the output should be int row-column system, and vise versa).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that accepts two square (`NxN`) matrices (two dimensional arrays), and returns the product of the two. Only square matrices will be given.

How to multiply two square matrices: 

We are given two matrices, A and B, of size 2x2 (note: tests are not limited to 2x2). Matrix C, the solution, will be equal to the product of A and B. To fill in cell `[0][0]` of matrix C, you need to compute: `A[0][0] * B[0][0] + A[0][1] * B[1][0]`.

More general: To fill in cell `[n][m]` of matrix C, you need to first multiply the elements in the nth row of matrix A by the elements in the mth column of matrix B, then take the sum of all those products. This will give you the value for cell `[m][n]` in matrix C. 

## Example
```
  A         B          C
|1 2|  x  |3 2|  =  | 5 4|
|3 2|     |1 1|     |11 8|
```

Detailed calculation:
```
C[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0] = 1*3 + 2*1 =  5
C[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1] = 1*2 + 2*1 =  4
C[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0] = 3*3 + 2*1 = 11
C[1][1] = A[1][0] * B[0][1] + A[1][1] * B[1][1] = 3*2 + 2*1 =  8
```
Link to Wikipedia explaining matrix multiplication (look at the square matrix example): 
http://en.wikipedia.org/wiki/Matrix_multiplication

A more visual explanation of matrix multiplication: http://matrixmultiplication.xyz

~~~if:c
**Note:** In **C**, the dimensions of both square matrices `n` will be passed into your function.  However, since the dimensions of your returned "matrix" is expected to be the same as that of the inputs, you will not need to keep track of the dimensions of your matrix in another variable.
~~~

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
It is known that fleas in Berland can jump only vertically and horizontally, and the length of the jump is always equal to *s* centimeters. A flea has found herself at the center of some cell of the checked board of the size *n*<=×<=*m* centimeters (each cell is 1<=×<=1 centimeters). She can jump as she wishes for an arbitrary number of times, she can even visit a cell more than once. The only restriction is that she cannot jump out of the board.

The flea can count the amount of cells that she can reach from the starting position (*x*,<=*y*). Let's denote this amount by *d**x*,<=*y*. Your task is to find the number of such starting positions (*x*,<=*y*), which have the maximum possible value of *d**x*,<=*y*.

Input Specification:
The first line contains three integers *n*, *m*, *s* (1<=≤<=*n*,<=*m*,<=*s*<=≤<=106) — length of the board, width of the board and length of the flea's jump.

Output Specification:
Output the only integer — the number of the required starting positions of the flea.

Demo Input:
['2 3 1000000\n', '3 3 2\n']

Demo Output:
['6\n', '4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Captain Bill the Hummingbird and his crew recieved an interesting challenge offer. Some stranger gave them a map, potion of teleportation and said that only this potion might help them to reach the treasure. 

Bottle with potion has two values x and y written on it. These values define four moves which can be performed using the potion:

  * <image>
  * <image>
  * <image>
  * <image>



Map shows that the position of Captain Bill the Hummingbird is (x1, y1) and the position of the treasure is (x2, y2).

You task is to tell Captain Bill the Hummingbird whether he should accept this challenge or decline. If it is possible for Captain to reach the treasure using the potion then output "YES", otherwise "NO" (without quotes).

The potion can be used infinite amount of times.

Input

The first line contains four integer numbers x1, y1, x2, y2 ( - 105 ≤ x1, y1, x2, y2 ≤ 105) — positions of Captain Bill the Hummingbird and treasure respectively.

The second line contains two integer numbers x, y (1 ≤ x, y ≤ 105) — values on the potion bottle.

Output

Print "YES" if it is possible for Captain to reach the treasure using the potion, otherwise print "NO" (without quotes).

Examples

Input

0 0 0 6
2 3


Output

YES


Input

1 1 3 6
1 5


Output

NO

Note

In the first example there exists such sequence of moves:

  1. <image> — the first type of move 
  2. <image> — the third type of move 

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