vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
John Doe started thinking about graphs. After some thought he decided that he wants to paint an undirected graph, containing exactly k cycles of length 3. 

A cycle of length 3 is an unordered group of three distinct graph vertices a, b and c, such that each pair of them is connected by a graph edge. 

John has been painting for long, but he has not been a success. Help him find such graph. Note that the number of vertices there shouldn't exceed 100, or else John will have problems painting it.


-----Input-----

A single line contains an integer k (1 ≤ k ≤ 10^5) — the number of cycles of length 3 in the required graph.


-----Output-----

In the first line print integer n (3 ≤ n ≤ 100) — the number of vertices in the found graph. In each of next n lines print n characters "0" and "1": the i-th character of the j-th line should equal "0", if vertices i and j do not have an edge between them, otherwise it should equal "1". Note that as the required graph is undirected, the i-th character of the j-th line must equal the j-th character of the i-th line. The graph shouldn't contain self-loops, so the i-th character of the i-th line must equal "0" for all i.


-----Examples-----
Input
1

Output
3
011
101
110

Input
10

Output
5
01111
10111
11011
11101
11110

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
You are given circular array *a*0,<=*a*1,<=...,<=*a**n*<=-<=1. There are two types of operations with it: 
 -  *inc*(*lf*,<=*rg*,<=*v*) — this operation increases each element on the segment [*lf*,<=*rg*] (inclusively) by *v*; -  *rmq*(*lf*,<=*rg*) — this operation returns minimal value on the segment [*lf*,<=*rg*] (inclusively). 
Assume segments to be circular, so if *n*<==<=5 and *lf*<==<=3,<=*rg*<==<=1, it means the index sequence: 3,<=4,<=0,<=1.

Write program to process given sequence of operations.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=200000). The next line contains initial state of the array: *a*0,<=*a*1,<=...,<=*a**n*<=-<=1 (<=-<=106<=≤<=*a**i*<=≤<=106), *a**i* are integer. The third line contains integer *m* (0<=≤<=*m*<=≤<=200000), *m* — the number of operartons. Next *m* lines contain one operation each. If line contains two integer *lf*,<=*rg* (0<=≤<=*lf*,<=*rg*<=≤<=*n*<=-<=1) it means *rmq* operation, it contains three integers *lf*,<=*rg*,<=*v* (0<=≤<=*lf*,<=*rg*<=≤<=*n*<=-<=1;<=-<=106<=≤<=*v*<=≤<=106) — *inc* operation.

Output Specification:
For each *rmq* operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Demo Input:
['4\n1 2 3 4\n4\n3 0\n3 0 -1\n0 1\n2 1\n']

Demo Output:
['1\n0\n0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Uttu got to know about an interesting two-player mobile game recently and invites his friend Gangwar to try it out with him. Gangwar, however, has been playing this game since it was out 5 years ago and is a Legendary Grandmaster at it. Uttu immediately thought of somehow cheating in this game to beat Gangwar.
But the most he could do was choose if he wanted to go "First" or if he wanted to go "Second" in this alternative turn based game. Help Uttu choose so that he will always win regardless of Gangwar's moves.Description of the game
You are playing on a continent name Tamriel. This continent have $N$ towns numbered from $1$ to $N$ where town $1$ is the capital. These towns are connected to each other by $N-1$ roads. Any two towns are connected by some series of roads, i.e., You can go from any town to any other town using these roads.
Each town $i$ some initial amout of soldiers $S_i$ in it. At every move, a player can choose a town other than the capital $i$ and move some non-zero amount of its current soldiers to a town which is one step closer towards the capital. After the first move, the moves are alternated between the players. The player who cannot make a move loses.Input
- The first line contains a single integer $N$
- The second line contains a $N$ space seperated integers denoting $S_1,S_2,\dots,S_n$
- The $N-1$ subsequent lines contain two space seperated integers $u$ and $v$, denoting that the town $u$ and town $v$ are connected by a road.Output
- Print "First" or "Second" based on what Uttu should choose to win.Constraints
- $ 2 \leq N \leq {2}\times{10}^{5}$
- $ 1 \leq S_i \leq {10}^{9}$ for each valid $i$
- $ 1 \leq u,v \leq N$Sample Input 1
2
10 10
1 2
Sample Output 1
First
Explanation 1
Uttu will move the $10$ soldiers at town $2$ to the capital (town $1$). After this Gangwar cannot make a move, so he loses.Sample Input 2
3
1 1 1
1 2
1 3
Sample Output 2
Second
Explanation 2
Gangwar has options: either move the soldier at town $2$, or move the soldier at town $3$.
Whatever he choses, Uttu will chose the other town's soldier to move. And then Gangwar loses.

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
A progress bar is an element of graphical interface that displays the progress of a process for this very moment before it is completed. Let's take a look at the following form of such a bar.

A bar is represented as *n* squares, located in line. To add clarity, let's number them with positive integers from 1 to *n* from the left to the right. Each square has saturation (*a**i* for the *i*-th square), which is measured by an integer from 0 to *k*. When the bar for some *i* (1<=≤<=*i*<=≤<=*n*) is displayed, squares 1,<=2,<=... ,<=*i*<=-<=1 has the saturation *k*, squares *i*<=+<=1,<=*i*<=+<=2,<=... ,<=*n* has the saturation 0, and the saturation of the square *i* can have any value from 0 to *k*.

So some first squares of the progress bar always have the saturation *k*. Some last squares always have the saturation 0. And there is no more than one square that has the saturation different from 0 and *k*.

The degree of the process's completion is measured in percents. Let the process be *t*% completed. Then the following inequation is fulfilled: 

An example of such a bar can be seen on the picture.

For the given *n*, *k*, *t* determine the measures of saturation for all the squares *a**i* of the progress bar.

Input Specification:
We are given 3 space-separated integers *n*, *k*, *t* (1<=≤<=*n*,<=*k*<=≤<=100, 0<=≤<=*t*<=≤<=100).

Output Specification:
Print *n* numbers. The *i*-th of them should be equal to *a**i*.

Demo Input:
['10 10 54\n', '11 13 37\n']

Demo Output:
['10 10 10 10 10 4 0 0 0 0 ', '13 13 13 13 0 0 0 0 0 0 0 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
You are given a string s consisting only of digits 0-9, commas ,, and dots .

Your task is to complete the regex_pattern defined below, which will be used to re.split() all of the , and . symbols in s.

It’s guaranteed that every comma and every dot in s is preceeded and followed by a digit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Rocky had participated in coding competition and he is sharing one of the problem with you which he was unable to solve. Help Rocky in solving the problem.
Suppose the alphabets are arranged in a row starting with index 0$0$ from AtoZ$A to Z$.
If in a coded language  A=27$A=27$ and AND=65$AND=65$.
Help Rocky to find a suitable formula for finding all the value for given test cases?
(All alphabets are in Upper case only).

-----Input:-----
First line of the input contains  string s$s$.

-----Output:-----
Output the possible integer values of the given string s$s$ according to the question . 

-----Constraints-----
- 1≤s≤100$1 \leq s \leq 100$

-----Sample Input:-----
A

AND   

-----Sample Output:-----
27

65

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya loves football very much. One day, as he was watching a football match, he was writing the players' current positions on a piece of paper. To simplify the situation he depicted it as a string consisting of zeroes and ones. A zero corresponds to players of one team; a one corresponds to players of another team. If there are at least 7 players of some team standing one after another, then the situation is considered dangerous. For example, the situation 00100110111111101 is dangerous and 11110111011101 is not. You are given the current situation. Determine whether it is dangerous or not.

Input Specification:
The first input line contains a non-empty string consisting of characters "0" and "1", which represents players. The length of the string does not exceed 100 characters. There's at least one player from each team present on the field.

Output Specification:
Print "YES" if the situation is dangerous. Otherwise, print "NO".

Demo Input:
['001001\n', '1000000001\n']

Demo Output:
['NO\n', 'YES\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bob is a farmer. He has a large pasture with many sheep. Recently, he has lost some of them due to wolf attacks. He thus decided to place some shepherd dogs in such a way that all his sheep are protected.

The pasture is a rectangle consisting of *R*<=×<=*C* cells. Each cell is either empty, contains a sheep, a wolf or a dog. Sheep and dogs always stay in place, but wolves can roam freely around the pasture, by repeatedly moving to the left, right, up or down to a neighboring cell. When a wolf enters a cell with a sheep, it consumes it. However, no wolf can enter a cell with a dog.

Initially there are no dogs. Place dogs onto the pasture in such a way that no wolf can reach any sheep, or determine that it is impossible. Note that since you have many dogs, you do not need to minimize their number.

Input Specification:
First line contains two integers *R* (1<=≤<=*R*<=≤<=500) and *C* (1<=≤<=*C*<=≤<=500), denoting the number of rows and the numbers of columns respectively.

Each of the following *R* lines is a string consisting of exactly *C* characters, representing one row of the pasture. Here, 'S' means a sheep, 'W' a wolf and '.' an empty cell.

Output Specification:
If it is impossible to protect all sheep, output a single line with the word "No".

Otherwise, output a line with the word "Yes". Then print *R* lines, representing the pasture after placing dogs. Again, 'S' means a sheep, 'W' a wolf, 'D' is a dog and '.' an empty space. You are not allowed to move, remove or add a sheep or a wolf.

If there are multiple solutions, you may print any of them. You don't have to minimize the number of dogs.

Demo Input:
['6 6\n..S...\n..S.W.\n.S....\n..W...\n...W..\n......\n', '1 2\nSW\n', '5 5\n.S...\n...S.\nS....\n...S.\n.S...\n']

Demo Output:
['Yes\n..SD..\n..SDW.\n.SD...\n.DW...\nDD.W..\n......\n', 'No\n', 'Yes\n.S...\n...S.\nS.D..\n...S.\n.S...\n']

Note:
In the first example, we can split the pasture into two halves, one containing wolves and one containing sheep. Note that the sheep at (2,1) is safe, as wolves cannot move diagonally.

In the second example, there are no empty spots to put dogs that would guard the lone sheep.

In the third example, there are no wolves, so the task is very easy. We put a dog in the center to observe the peacefulness of the meadow, but the solution would be correct even without him.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Calvin the robot lies in an infinite rectangular grid. Calvin's source code contains a list of n commands, each either 'U', 'R', 'D', or 'L' — instructions to move a single square up, right, down, or left, respectively. How many ways can Calvin execute a non-empty contiguous substrings of commands and return to the same square he starts in? Two substrings are considered different if they have different starting or ending indices.


-----Input-----

The first line of the input contains a single positive integer, n (1 ≤ n ≤ 200) — the number of commands.

The next line contains n characters, each either 'U', 'R', 'D', or 'L' — Calvin's source code.


-----Output-----

Print a single integer — the number of contiguous substrings that Calvin can execute and return to his starting square.


-----Examples-----
Input
6
URLLDR

Output
2

Input
4
DLUU

Output
0

Input
7
RLRLRLR

Output
12



-----Note-----

In the first case, the entire source code works, as well as the "RL" substring in the second and third characters.

Note that, in the third case, the substring "LR" appears three times, and is therefore counted three times to the total result.

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

Time Limit: 3 seconds

Memory Limit: 256 megabytes

Problem Description:
Karlsson has visited Lillebror again. They found a box of chocolates and a big whipped cream cake at Lillebror's place. Karlsson immediately suggested to divide the sweets fairly between Lillebror and himself. Specifically, to play together a game he has just invented with the chocolates. The winner will get the cake as a reward.

The box of chocolates has the form of a hexagon. It contains 19 cells for the chocolates, some of which contain a chocolate. The players move in turns. During one move it is allowed to eat one or several chocolates that lay in the neighboring cells on one line, parallel to one of the box's sides. The picture below shows the examples of allowed moves and of an unacceptable one. The player who cannot make a move loses.

Karlsson makes the first move as he is Lillebror's guest and not vice versa. The players play optimally. Determine who will get the cake.

Input Specification:
The input data contains 5 lines, containing 19 words consisting of one symbol. The word "O" means that the cell contains a chocolate and a "." stands for an empty cell. It is guaranteed that the box contains at least one chocolate. See the examples for better understanding.

Output Specification:
If Karlsson gets the cake, print "Karlsson" (without the quotes), otherwise print "Lillebror" (yet again without the quotes).

Demo Input:
['. . .\n . . O .\n. . O O .\n . . . .\n  . . .\n', '. . .\n . . . O\n. . . O .\n O . O .\n  . O .\n']

Demo Output:
['Lillebror', 'Karlsson']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string $s$ of length $n$ can be encrypted by the following algorithm:  iterate over all divisors of $n$ in decreasing order (i.e. from $n$ to $1$),  for each divisor $d$, reverse the substring $s[1 \dots d]$ (i.e. the substring which starts at position $1$ and ends at position $d$). 

For example, the above algorithm applied to the string $s$="codeforces" leads to the following changes: "codeforces" $\to$ "secrofedoc" $\to$ "orcesfedoc" $\to$ "rocesfedoc" $\to$ "rocesfedoc" (obviously, the last reverse operation doesn't change the string because $d=1$).

You are given the encrypted string $t$. Your task is to decrypt this string, i.e., to find a string $s$ such that the above algorithm results in string $t$. It can be proven that this string $s$ always exists and is unique.


-----Input-----

The first line of input consists of a single integer $n$ ($1 \le n \le 100$) — the length of the string $t$. The second line of input consists of the string $t$. The length of $t$ is $n$, and it consists only of lowercase Latin letters.


-----Output-----

Print a string $s$ such that the above algorithm results in $t$.


-----Examples-----
Input
10
rocesfedoc

Output
codeforces

Input
16
plmaetwoxesisiht

Output
thisisexampletwo

Input
1
z

Output
z



-----Note-----

The first example is described in the problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kirill And The Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kirill plays a new computer game. He came to the potion store where he can buy any potion. Each potion is characterized by two integers — amount of experience and cost. The efficiency of a potion is the ratio of the amount of experience to the cost. Efficiency may be a non-integer number.

For each two integer numbers *a* and *b* such that *l*<=≤<=*a*<=≤<=*r* and *x*<=≤<=*b*<=≤<=*y* there is a potion with experience *a* and cost *b* in the store (that is, there are (*r*<=-<=*l*<=+<=1)·(*y*<=-<=*x*<=+<=1) potions).

Kirill wants to buy a potion which has efficiency *k*. Will he be able to do this?

Input Specification:
First string contains five integer numbers *l*, *r*, *x*, *y*, *k* (1<=≤<=*l*<=≤<=*r*<=≤<=107, 1<=≤<=*x*<=≤<=*y*<=≤<=107, 1<=≤<=*k*<=≤<=107).

Output Specification:
Print "YES" without quotes if a potion with efficiency exactly *k* can be bought in the store and "NO" without quotes otherwise.

You can output each of the letters in any register.

Demo Input:
['1 10 1 10 1\n', '1 5 6 10 1\n']

Demo Output:
['YES', 'NO']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a simple arithmetic expression of the form a?b, where a and b are integer constants, and ? can be one of the following operations: '+' (addition), '-' (subtraction), '*' (multiplication), '/' (integer division) or '%' (modulo operation).

Output the result of evaluation of this expression.

Input

The input is a single line containing an expression a?b. Here a and b are integers between 1 and 999, inclusive; ? is an operation character: '+', '-' (ASCII code 45), '*', '/' or '%'.

Output

Output a single integer — the result of evaluation of this expression.

Examples

Input

123+456


Output

579


Input

192/5


Output

38


Input

945%19


Output

14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Does the card fit in a snack? (Are Cards Snacks?)

square1001 You have $ N $ cards.

Each of these cards has an integer written on it, and the integer on the $ i $ th card is $ A_i $.

square1001 Your random number today is $ K $. square1001 You want to choose some of these $ N $ cards so that they add up to $ K $.

E869120, who was watching this situation, wanted to prevent this.

Specifically, I want to eat a few cards in advance so that square1001 doesn't add up to $ K $ no matter how you choose the rest of the cards.

However, E869120 is full and I don't want to eat cards as much as possible.

Now, how many cards can you eat at least E869120 to prevent this?

input

Input is given from standard input in the following format.


$ N $ $ K $
$ A_1 $ $ A_2 $ $ A_3 $ $ \ cdots $ $ A_N $


output

E869120 Print the minimum number of cards you eat to achieve your goal in one line.

However, insert a line break at the end.

Constraint

* $ 1 \ leq N \ leq 20 $
* $ 1 \ leq K \ leq 1000000000 \ (= 10 ^ 9) $
* $ 0 \ leq A_i \ leq 1000000 \ (= 10 ^ 6) $
* All inputs are integers.



Input example 1


5 9
8 6 9 1 2


Output example 1


2


For example, you can thwart square1001's purpose by eating the third card (which has a 9) and the fourth card (which has a 1).

Input example 2


8 2
1 1 1 1 1 1 1 1


Output example 2


7


Input example 3


20 200
31 12 21 17 19 29 25 40 5 8 32 1 27 20 31 13 35 1 8 5


Output example 3


6






Example

Input

5 9
8 6 9 1 2


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Toad Pimple has an array of integers $a_1, a_2, \ldots, a_n$.

We say that $y$ is reachable from $x$ if $x<y$ and there exists an integer array $p$ such that $x = p_1 < p_2 < \ldots < p_k=y$, and $a_{p_i}\, \&\, a_{p_{i+1}} > 0$ for all integers $i$ such that $1 \leq i < k$.

Here $\&$ denotes the bitwise AND operation.

You are given $q$ pairs of indices, check reachability for each of them.


-----Input-----

The first line contains two integers $n$ and $q$ ($2 \leq n \leq 300\,000$, $1 \leq q \leq 300\,000$) — the number of integers in the array and the number of queries you need to answer.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 300\,000$) — the given array.

The next $q$ lines contain two integers each. The $i$-th of them contains two space-separated integers $x_i$ and $y_i$ ($1 \leq x_i < y_i \leq n$). You need to check if $y_i$ is reachable from $x_i$. 


-----Output-----

Output $q$ lines. In the $i$-th of them print "Shi" if $y_i$ is reachable from $x_i$, otherwise, print "Fou".


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

Output
Fou
Shi
Shi



-----Note-----

In the first example, $a_3 = 0$. You can't reach it, because AND with it is always zero. $a_2\, \&\, a_4 > 0$, so $4$ is reachable from $2$, and to go from $1$ to $4$ you can use $p = [1, 2, 4]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given an integer N and a digit D. Find the minimum non-negetive integer you should add to N such that the final value of N does not contain the digit D.

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

- The first line contains T denoting the number of test cases. Then the test cases follow.
- Each test case contains two integers N and D on a single line denoting the original number and the digit you need to avoid.

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

For each test case, output on a single line the minimum non-negetive integer you should add to N.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$
$0 ≤ D ≤ 9$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
5
21 5
8 8
100 0
5925 9
434356 3

----- Sample Output 1 ------ 
0
1
11
75
5644

----- explanation 1 ------ 
Test case $1$: $N = 21$ does not contain the digit $D = 5$. Hence there is no need to add any integers to $N$. 

Test case $2$: If $1$ is added to $N = 8$, it becomes equal to $9$, which does not contain the digit $D = 8$.

Test case $3$: The minimum integer you should add to $N = 100$ such that the final value of $N$ does not contain the digit $D = 0$ is $11$.

Test case $5$: The minimum integer which is greater than $434356$ and does not contain the digit $D = 3$ is $440000$. So we should add $440000 - 434356 = 5644$.

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