vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
On the coordinate plane there is a square with sides parallel to the coordinate axes. The length of the square side is equal to a. The lower left corner of the square coincides with the point (0, 0) (the point of the origin). The upper right corner of the square has positive coordinates.

You are given a point with coordinates (x, y). Your task is to determine whether this point is located strictly inside the square, on its side, or strictly outside the square.

Input

The first line contains three integers a, x and y (1 ≤ a ≤ 1000,  - 1000 ≤ x, y ≤ 1000) — the length of the square side and the coordinates of the point which should be checked.

Output

Print one integer:

  * 0, if the point is located strictly inside the square; 
  * 1, if the point is located on the side of the square; 
  * 2, if the point is located strictly outside the square. 

Examples

Input

2 1 1


Output

0


Input

4 4 4


Output

1


Input

10 5 -4


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call a string good if and only if it consists of only two types of letters — 'a' and 'b' and every two consecutive letters are distinct. For example "baba" and "aba" are good strings and "abb" is a bad string.

You have $a$ strings "a", $b$ strings "b" and $c$ strings "ab". You want to choose some subset of these strings and concatenate them in any arbitrarily order.

What is the length of the longest good string you can obtain this way?


-----Input-----

The first line contains three positive integers $a$, $b$, $c$ ($1 \leq a, b, c \leq 10^9$) — the number of strings "a", "b" and "ab" respectively.


-----Output-----

Print a single number — the maximum possible length of the good string you can obtain.


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

Output
4

Input
2 1 2

Output
7

Input
3 5 2

Output
11

Input
2 2 1

Output
6

Input
1000000000 1000000000 1000000000

Output
4000000000



-----Note-----

In the first example the optimal string is "baba".

In the second example the optimal string is "abababa".

In the third example the optimal string is "bababababab".

In the fourth example the optimal string is "ababab".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rahul's Dad is the CEO of one of the leading companies. Every time somebody seeks for an appointment he calls up his secretary and asks her whether the day is a Sunday or not. He has to keep his caller on hold and is unhappy about it. Knowing that his son Mayank knows a bit of programming he asks him to make  a program to help him find all the sundays in a given month of a specific year.

Input:
The first Line contains t an integer, the number of test cases. The next t lines contain to integers first the year and then month.
Output:
Output consists of t lines containing the dates of sundays in that particular month

Constraints :
t<100000, month ≤ 12, 2000 ≤ year ≤ 5000

Test cases updated.. You may submit now

SAMPLE INPUT
2
3 2013
5 2010

SAMPLE OUTPUT
3 10 17 24 31
2 9 16 23 30

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
As Valeric and Valerko were watching one of the last Euro Championship games in a sports bar, they broke a mug. Of course, the guys paid for it but the barman said that he will let them watch football in his bar only if they help his son complete a programming task. The task goes like that.

Let's consider a set of functions of the following form: 

Valeric and Valerko really want to watch the next Euro Championship game, so they asked you to help them.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of functions. Each of the following *n* lines contains two space-separated integer numbers *k**i*,<=*b**i* (<=-<=109<=≤<=*k**i*,<=*b**i*<=≤<=109) that determine the *i*-th function.

Output Specification:
Print a single number — the number of angles that do not equal 180 degrees in the graph of the polyline that equals the sum of the given functions.

Demo Input:
['1\n1 0\n', '3\n1 0\n0 2\n-1 1\n', '3\n-2 -4\n1 7\n-5 1\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vlad and Nastya live in a city consisting of $n$ houses and $n-1$ road. From each house, you can get to the other by moving only along the roads. That is, the city is a tree.

Vlad lives in a house with index $x$, and Nastya lives in a house with index $y$. Vlad decided to visit Nastya. However, he remembered that he had postponed for later $k$ things that he has to do before coming to Nastya. To do the $i$-th thing, he needs to come to the $a_i$-th house, things can be done in any order. In $1$ minute, he can walk from one house to another if they are connected by a road.

Vlad does not really like walking, so he is interested what is the minimum number of minutes he has to spend on the road to do all things and then come to Nastya. Houses $a_1, a_2, \dots, a_k$ he can visit in any order. He can visit any house multiple times (if he wants).


-----Input-----

The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of input test cases. There is an empty line before each test case.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2\cdot 10^5$) — the number of houses and things, respectively.

The second line of each test case contains two integers $x$ and $y$ ($1 \le x, y \le n$) — indices of the houses where Vlad and Nastya live, respectively.

The third line of each test case contains $k$ integers $a_1, a_2, \dots, a_k$ ($1 \le a_i \le n$) — indices of houses Vlad need to come to do things.

The following $n-1$ lines contain description of city, each line contains two integers $v_j$ and $u_j$ ($1 \le u_j, v_j \le n$) — indices of houses connected by road $j$.

It is guaranteed that the sum of $n$ for all cases does not exceed $2\cdot10^5$.


-----Output-----

Output $t$ lines, each of which contains the answer to the corresponding test case of input. As an answer output single integer — the minimum number of minutes Vlad needs on the road to do all the things and come to Nastya.


-----Examples-----

Input
3
3 1
1 3
2
1 3
1 2
6 4
3 5
1 6 2 1
1 3
3 4
3 5
5 6
5 2
6 2
3 2
5 3
1 3
3 4
3 5
5 6
5 2
Output
3
7
2


-----Note-----

Tree and best path for the first test case:

$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$

Tree and best path for the second test case:

$3 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 5 \rightarrow 6 \rightarrow 5$

Tree and best path for the third test case:

$3 \rightarrow 5 \rightarrow 2$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every character in the string “IITMANDI” is given a certain number of points. You are given a scrabble board with only one row. The input contains the positions of score modifiers such as: Double Letter, Triple Letter, Double Word and Triple Word. You need to find the best position to place the string “IITMANDI” such that your score is maximized. 
Double Letter - Doubles the number of points you get for the letter placed on the double letter.
Triple Letter - Triples the number of points you get for the letter placed on the triple letter.
Double Word - Doubles the number of points you get for the word. Applied after applying above modifiers.
Triple Word - Triples the number of points you get for the word. Applied after applying the above modifiers.
The word has to be read from left to right. You can’t place it in the reverse direction.

The letters have to be placed continuously on the board.

If there is no modifier or a double word or triple word modifier before a tile, it's score is added to the total score. The double word and triple modifiers are applied at the end.

-----Input Format-----
- First line containes a single integer $T$ - the number of test cases.
- First line of each test case contains a single integer $N$ - the size of the board.    
- Second line of each test case contains a string of size $N$ representing the board according to the following convention:

'.' - No modifier

'd' - Double letter

't' - Triple letter

'D' - Double word

'T' - Triple word     
- Third line of each test case contains 8 integers corresponding to the points associated with each letter of the string "IITMANDI". Note that the 3 'I's in IITMANDI cannot be interchanged freely. The score of the first 'I' will be equal to the first integer, score of the second 'I' will be equal to the second integer and the score of the last 'I' will be equal to the last integer.

-----Output Format-----
For each test case, output a single integer in a new line, the maximum possible score. 

-----Constraints-----
$ 1 \leq T \leq 1000 $
$ 8 \leq N \leq 100 $
$ 0 \leq $ Points for each character $ \leq 10^5 $ 

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

10

..d.t.D..d

10 11 12 9 8 10 11 15

22

dtDtTD..ddT.TtTdDT..TD

12297 5077 28888 17998 12125 27400 31219 21536

-----Sample Output-----
270

35629632

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a chessboard of size $n \times n$. It is filled with numbers from $1$ to $n^2$ in the following way: the first $\lceil \frac{n^2}{2} \rceil$ numbers from $1$ to $\lceil \frac{n^2}{2} \rceil$ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest $n^2 - \lceil \frac{n^2}{2} \rceil$ numbers from $\lceil \frac{n^2}{2} \rceil + 1$ to $n^2$ are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation $\lceil\frac{x}{y}\rceil$ means division $x$ by $y$ rounded up.

For example, the left board on the following picture is the chessboard which is given for $n=4$ and the right board is the chessboard which is given for $n=5$. [Image] 

You are given $q$ queries. The $i$-th query is described as a pair $x_i, y_i$. The answer to the $i$-th query is the number written in the cell $x_i, y_i$ ($x_i$ is the row, $y_i$ is the column). Rows and columns are numbered from $1$ to $n$.


-----Input-----

The first line contains two integers $n$ and $q$ ($1 \le n \le 10^9$, $1 \le q \le 10^5$) — the size of the board and the number of queries.

The next $q$ lines contain two integers each. The $i$-th line contains two integers $x_i, y_i$ ($1 \le x_i, y_i \le n$) — description of the $i$-th query.


-----Output-----

For each query from $1$ to $q$ print the answer to this query. The answer to the $i$-th query is the number written in the cell $x_i, y_i$ ($x_i$ is the row, $y_i$ is the column). Rows and columns are numbered from $1$ to $n$. Queries are numbered from $1$ to $q$ in order of the input.


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

Output
1
8
16
13
4

Input
5 4
2 1
4 2
3 3
3 4

Output
16
9
7
20



-----Note-----

Answers to the queries from examples are on the board in the picture from the problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N ninjas in a hidden ninja village. The main source of this village's income is the fees of the jobs completed by these N ninja. These N ninja follow a linear heirarchy. You are given the number of messages ninja i sends to ninja j during a mission. Your job is to output the hierarchy of these ninja which minimizes the number of messages sent from lower ranked ninjas to higher ranked ninjas. If multiple solutions are possible, return the lexicographically smallest solution.

Input Format The first line will contain the number of test cases T. T test cases will then follow.

For each test case, the first line will contain the number of ninjas N.

This will be followed by N lines. Each of these N lines will contain N integers each.

i'th number in line j denotes the number of messages sent by ninja j to ninja i.

Constraints

1 ≤ T ≤ 10

2 ≤ N ≤ 15

0 ≤ no. of messages from one ninja to another ≤ 9

Output Format Output T lines for T test cases. For each test case, output the ninjas in decreasing order of their ranks.

SAMPLE INPUT
2
3
0 0 0
1 0 0
0 1 0
6
0 1 2 1 0 5
6 0 1 7 4 5
8 3 0 4 7 9
0 4 3 0 8 6
3 4 9 9 0 4
6 4 9 8 1 0

SAMPLE OUTPUT
2 1 0
4 2 1 5 0 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mathematics wrapped in English is not that Easy

Love stories that happened in college life stays for longer , even for a life-time. Ramanuj and Alice's love story is one of them. How they both fall for each-other only the past knows. 

Alice who was talented in English subject whereas Ramanuj was talented in Mathematics subject. After college they both got married with each-other. 

After years of their successful married life , Alice wanted to re-live their love story life when they were in college. She remember about the game they both had played very much.

The game was as simple as doing calculation in Mathematics. Alice used to write any Mathematical operation in English and Ramanuj used to solve it to impress her. For example , let say mathematical of '2 + 2' is written as '2PLUS2' in English , and the result is '4' .

After years Ramanuj can't solve Alice's question on his own , so he asked you for your help. Solve it for Ramanuj and Alice.

Input : First line will contains an integer T number of test cases. Next T lines will contain S ,  single string of operation you have to solve.

Output : Produce required output for each test case in new line.

Note : You have to follow Precedence Order of Operators. And final answer should be an integer. Output can be a large value so output your result as modulo 10^9

Constraints

1 ≤ T ≤ 100

SAMPLE INPUT
5
2PLUS2MULTIPLY6DIVIDE2MINUS1
21PLUS59MINUS94MINUS93MINUS15MULTIPLY50
66MINUS39MULTIPLY54DIVIDE32MINUS48MULTIPLY71
33PLUS41MULTIPLY15MULTIPLY83MULTIPLY52PLUS25
7DIVIDE7MULTIPLY84MINUS88MINUS7MULTIPLY39

SAMPLE OUTPUT
7
-857
-3407
2654398
-277

Explanation

Case 1 Explanation ,  Input String can be re-written as shown below (with spacing). Now when we follow the Precedence Order of Operators the below written steps shows the performed operation on given string. And at end we get 7 as our final result.

2 PLUS 2 MULTIPLY 6 DIVIDE 2 MINUS 1

2 PLUS 12 DIVIDE 2 MINUS 1

2 PLUS 6 MINUS 1

8 MINUS 1

7

If we solve the other cases according to Precedence Order of operators , we get the following results.

Case 2 : -857

Case 3 : -3407

Case 4 : 2654398

Case 5 : -277

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Pari and Arya did some research about NP-Hard problems and they found the minimum vertex cover problem very interesting.

Suppose the graph G is given. Subset A of its vertices is called a vertex cover of this graph, if for each edge uv there is at least one endpoint of it in this set, i.e. $u \in A$ or $v \in A$ (or both).

Pari and Arya have won a great undirected graph as an award in a team contest. Now they have to split it in two parts, but both of them want their parts of the graph to be a vertex cover.

They have agreed to give you their graph and you need to find two disjoint subsets of its vertices A and B, such that both A and B are vertex cover or claim it's impossible. Each vertex should be given to no more than one of the friends (or you can even keep it for yourself).


-----Input-----

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively.

Each of the next m lines contains a pair of integers u_{i} and v_{i} (1  ≤  u_{i},  v_{i}  ≤  n), denoting an undirected edge between u_{i} and v_{i}. It's guaranteed the graph won't contain any self-loops or multiple edges.


-----Output-----

If it's impossible to split the graph between Pari and Arya as they expect, print "-1" (without quotes).

If there are two disjoint sets of vertices, such that both sets are vertex cover, print their descriptions. Each description must contain two lines. The first line contains a single integer k denoting the number of vertices in that vertex cover, and the second line contains k integers — the indices of vertices. Note that because of m ≥ 1, vertex cover cannot be empty.


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

Output
1
2 
2
1 3 

Input
3 3
1 2
2 3
1 3

Output
-1



-----Note-----

In the first sample, you can give the vertex number 2 to Arya and vertices numbered 1 and 3 to Pari and keep vertex number 4 for yourself (or give it someone, if you wish).

In the second sample, there is no way to satisfy both Pari and Arya.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
You are given a valid XML document, and you have to print its score. The score is calculated by the sum of the score of each element. For any element, the score is equal to the number of attributes it has.

=====Input Format=====
The first line contains N, the number of lines in the XML document.
The next N lines follow containing the XML document.

=====Output Format=====
Output a single line, the integer score of the given XML document.

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

Template in C

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 1000
* 1 ≤ timei ≤ 50000
* 1 ≤ length of namei ≤ 10
* 1 ≤ Sum of timei ≤ 1000000

Input

n q
name1 time1
name2 time2
...
namen timen


In the first line the number of processes n and the quantum q are given separated by a single space.

In the following n lines, names and times for the n processes are given. namei and timei are separated by a single space.

Output

For each process, prints its name and the time the process finished in order.

Example

Input

5 100
p1 150
p2 80
p3 200
p4 350
p5 20


Output

p2 180
p5 400
p1 450
p3 550
p4 800

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef’s girlfriend is angry with him because he forgot her birthday. Chef decided to please her by gifting her a Love Graph. 
Chef has $N$ vertices: $V_1, V_2, \dots, V_N$. Love Graph is an undirected multigraph with no self-loops and can be constructed by performing the following operations:-
- Choose an integer $i$ ($1 \leq i \leq N$)
- Choose another integer $j \space \space \{ (i \neq j) \text{ and } (1 \leq j \leq N) \}$
- Make an edge between $V_i$ and $V_j$
- Set $i = j$
- Repeat steps $2, 3$ and $4$ in order $M-1$ more times.
Find the number of ways in which Chef can construct a Love Graph. Since the answer can be very large, compute it modulo $10^9+7$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. 
- The first line of each test case contains two space-separated integers $N$ and $M$.

-----Output-----
For each test case, print a single line containing one integer — the number of ways in which Chef can construct a Love Graph modulo $10^9+7$.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $2 \leq N \leq 10^9$
- $1 \leq M \leq 10^{18}$

-----Subtasks-----
- 30 points:
- $1 \leq T \leq 100$
- $2 \leq N \leq 10$
- $1 \leq M \leq 10$ 
- 70 points: original constraints

-----Sample Input-----
1

2 1   

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

-----Explanation-----
There are two ways of constructing Love Graph.

In first way, we pick Vertex 1 and then join with Vertex 2.

In second way, we pick Vertex 2 and then join with Vertex 1.

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

Make a custom esolang interpreter for the language [InfiniTick](https://esolangs.org/wiki/InfiniTick). InfiniTick is a descendant of [Tick](https://esolangs.org/wiki/tick) but also very different. Unlike Tick, InfiniTick has 8 commands instead of 4. It also runs infinitely, stopping the program only when an error occurs. You may choose to do the [Tick](https://www.codewars.com/kata/esolang-tick) kata first.

Syntax/Info
======

InfiniTick runs in an infinite loop. This makes it both harder and easier to program in. It has an infinite memory of bytes and an infinite output amount. The program only stops when an error is reached. The program is also supposed to ignore non-commands.

Commands
======

`>`: Move data selector right.

`<`: Move data selector left.

`+`: Increment amount of memory cell. Truncate overflow: 255+1=0.

`-`: Decrement amount of memory cell. Truncate overflow: 0-1=255.

`*`: Add ascii value of memory cell to the output tape.

`&`: Raise an error, ie stop the program.

`/`: Skip next command if cell value is zero.

`\`: Skip next command if cell value is nonzero.

Examples
======

**Hello world!**

The following is a valid hello world program in InfiniTick.

```
'++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++**>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*>++++++++++++++++++++++++++++++++*>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*<<*>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*<<<<*>>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*>+++++++++++++++++++++++++++++++++*&'
```

Notes
======

* Please be wordy and post your likes/dislikes in the discourse area.
* If this kata is a duplicate or uses incorrect style, this is not an issue, this is a suggestion.
* Please don't edit this kata just to change the estimated rank. Thank you!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two strings s1 and s2. The task is to check if s2 is a rotated version of the string s1. The characters in the strings are in lowercase.
 
Example 1:
Input:
geeksforgeeks
forgeeksgeeks
Output: 
1
Explanation: s1 is geeksforgeeks, s2 is
forgeeksgeeks. Clearly, s2 is a rotated
version of s1 as s2 can be obtained by
left-rotating s1 by 5 units.
 
Example 2:
Input:
mightandmagic
andmagicmigth
Output: 
0
Explanation: Here with any amount of
rotation s2 can't be obtained by s1.
 
Your Task:
The task is to complete the function areRotations() which checks if the two strings are rotations of each other. The function returns true if string 1 can be obtained by rotating string 2, else it returns false.
 
Expected Time Complexity: O(N).
Expected Space Complexity: O(N).
Note: N = |s1|.
 
Constraints:
1 <= |s1|, |s2| <= 10^{7}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the function p(x), where x is an array of m integers, which returns an array y consisting of m + 1 integers such that y_{i} is equal to the sum of first i elements of array x (0 ≤ i ≤ m).

You have an infinite sequence of arrays A^0, A^1, A^2..., where A^0 is given in the input, and for each i ≥ 1 A^{i} = p(A^{i} - 1). Also you have a positive integer k. You have to find minimum possible i such that A^{i} contains a number which is larger or equal than k.


-----Input-----

The first line contains two integers n and k (2 ≤ n ≤ 200000, 1 ≤ k ≤ 10^18). n is the size of array A^0.

The second line contains n integers A^0_0, A^0_1... A^0_{n} - 1 — the elements of A^0 (0 ≤ A^0_{i} ≤ 10^9). At least two elements of A^0 are positive.


-----Output-----

Print the minimum i such that A^{i} contains a number which is larger or equal than k.


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

Output
1

Input
3 6
1 1 1

Output
2

Input
3 1
1 0 1

Output
0

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