vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Vlad went into his appartment house entrance, now he is on the $1$-th floor. He was going to call the elevator to go up to his apartment.

There are only two elevators in his house. Vlad knows for sure that:

the first elevator is currently on the floor $a$ (it is currently motionless),

the second elevator is located on floor $b$ and goes to floor $c$ ($b \ne c$). Please note, if $b=1$, then the elevator is already leaving the floor $1$ and Vlad does not have time to enter it.

If you call the first elevator, it will immediately start to go to the floor $1$. If you call the second one, then first it will reach the floor $c$ and only then it will go to the floor $1$. It takes $|x - y|$ seconds for each elevator to move from floor $x$ to floor $y$.

Vlad wants to call an elevator that will come to him faster. Help him choose such an elevator.


-----Input-----

The first line of the input contains the only $t$ ($1 \le t \le 10^4$) — the number of test cases.

This is followed by $t$ lines, three integers each $a$, $b$ and $c$ ($1 \le a, b, c \le 10^8$, $b \ne c$) — floor numbers described in the statement.


-----Output-----

Output $t$ numbers, each of which is the answer to the corresponding test case. As an answer, output:

$1$, if it is better to call the first elevator;

$2$, if it is better to call the second one;

$3$, if it doesn't matter which elevator to call (both elevators will arrive in the same time).


-----Examples-----

Input
3
1 2 3
3 1 2
3 2 1
Output
1
3
2


-----Note-----

In the first test case of the example, the first elevator is already on the floor of $1$.

In the second test case of the example, when called, the elevators would move as follows:

At the time of the call, the first elevator is on the floor of $3$, and the second one is on the floor of $1$, but is already going to another floor;

in $1$ second after the call, the first elevator would be on the floor $2$, the second one would also reach the floor $2$ and now can go to the floor $1$;

in $2$ seconds, any elevator would reach the floor $1$.

In the third test case of the example, the first elevator will arrive in $2$ seconds, and the second in $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N non-negative integers written on a blackboard. The i-th integer is A_i.

Takahashi can perform the following two kinds of operations any number of times in any order:

* Select one integer written on the board (let this integer be X). Write 2X on the board, without erasing the selected integer.
* Select two integers, possibly the same, written on the board (let these integers be X and Y). Write X XOR Y (XOR stands for bitwise xor) on the blackboard, without erasing the selected integers.



How many different integers not exceeding X can be written on the blackboard? We will also count the integers that are initially written on the board. Since the answer can be extremely large, find the count modulo 998244353.

Constraints

* 1 \leq N \leq 6
* 1 \leq X < 2^{4000}
* 1 \leq A_i < 2^{4000}(1\leq i\leq N)
* All input values are integers.
* X and A_i(1\leq i\leq N) are given in binary notation, with the most significant digit in each of them being 1.

Input

Input is given from Standard Input in the following format:


N X
A_1
:
A_N


Output

Print the number of different integers not exceeding X that can be written on the blackboard.

Examples

Input

3 111
1111
10111
10010


Output

4


Input

4 100100
1011
1110
110101
1010110


Output

37


Input

4 111001100101001
10111110
1001000110
100000101
11110000011


Output

1843


Input

1 111111111111111111111111111111111111111111111111111111111111111
1


Output

466025955

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given the `length` and `width` of a 4-sided polygon. The polygon can either be a rectangle or a square. 
If it is a square, return its area. If it is a rectangle, return its perimeter.

```
area_or_perimeter(6, 10) --> 32
area_or_perimeter(4, 4) --> 16
```

> Note: for the purposes of this kata you will assume that it is a square if its `length` and `width` are equal, otherwise it is a rectangle.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
George woke up and saw the current time *s* on the digital clock. Besides, George knows that he has slept for time *t*. 

Help George! Write a program that will, given time *s* and *t*, determine the time *p* when George went to bed. Note that George could have gone to bed yesterday relatively to the current time (see the second test sample).

Input Specification:
The first line contains current time *s* as a string in the format "hh:mm". The second line contains time *t* in the format "hh:mm" — the duration of George's sleep. It is guaranteed that the input contains the correct time in the 24-hour format, that is, 00<=≤<=*hh*<=≤<=23, 00<=≤<=*mm*<=≤<=59.

Output Specification:
In the single line print time *p* — the time George went to bed in the format similar to the format of the time in the input.

Demo Input:
['05:50\n05:44\n', '00:00\n01:00\n', '00:01\n00:00\n']

Demo Output:
['00:06\n', '23:00\n', '00:01\n']

Note:
In the first sample George went to bed at "00:06". Note that you should print the time only in the format "00:06". That's why answers "0:06", "00:6" and others will be considered incorrect. 

In the second sample, George went to bed yesterday.

In the third sample, George didn't do to bed at all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are working at a lower league football stadium and you've been tasked with automating the scoreboard.

The referee will shout out the score, you have already set up the voice recognition module which turns the ref's voice into a string, but the spoken score needs to be converted into a pair for the scoreboard!

e.g. `"The score is four nil"` should return `[4,0]`

Either teams score has a range of 0-9, and the ref won't say the same string every time e.g. 
      
    "new score: two three"
      
    "two two"
      
    "Arsenal just conceded another goal, two nil"
    
Note:
```python
Please return an array
```

Please rate and enjoy!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Professor Sahil is a master artist, he always finds creative ways to teach lessons to his students.
Today in Painting class he took all the students of the class to a wall. Professor Sahil asked every student to paint the wall upto a certain integral height one by one (second boy starts once the first boy finishes painting) from the bottom with any color of their wish, except a student Mudit who was made to stand behind the wall and note down all the data i.e the height upto which each student painted and the color $Ci$ every student used. At the end of the painting session Professor asked Mudit to tell how many distinct colors are there on the wall. Mudit being a weak student asked you for help.

Formally, given a wall of infinite height, initially unpainted. There occur $N$ operations, and in ith operation, the wall is painted upto height $Hi$ with color $Ci$. Suppose in jth operation (j>i) wall is painted upto height $Hj$ with color $Cj$ such that $Hj$ ≥ $Hi$, the $Cith$ color on the wall is hidden. At the end of $N$ operations, you have to find the number of distinct colors(≥1) visible on the wall.

Help him find out the number of distinct colors on the wall.

------ Input: ------

The first line consists of single integer $T$ denoting the number of test cases.
The second line contains 2 space separated integers $N$ and $M$, denoting the number of students and number of colors available (1 to $M$).
The third line contains $N$-space separated integers ($Hi$ ) denoting the height upto which each student painted the wall.
The fourth line contains $N$ space separated integers denoting the color ( $Ci$ ) the ith student used.

------ Output: ------
Print the number for distinct colors on the wall for each test case.

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ,M ≤ 10^{5}$
Sum of N over all test cases ≤ $5*10^{5}$
Sum of M over all test cases ≤$5*10^{5}$
$1 ≤ Hi ≤10^{9}$
$1 ≤ Ci ≤ M$

------ Sample Input: ------
	
------ Sample Output: ------
	
###EXPLANATION:

----- Sample Input 1 ------ 
3
5 4
1 2 3 4 5
3 3 3 3 3
5 4
3 5 1 2 3
1 2 3 4 3
5 5 
5 4 3 2 3
1 2 3 4 5
----- Sample Output 1 ------ 
1
2
3
----- explanation 1 ------ 
In the first test case, painted upto height 1, 2, 3, 4, 5 in the five operations, all with the same color. Hence, the number of distinct colors is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Valentina's birthday is coming soon!
Her parents love her so much that they are preparing some gifts to give her.
Valentina is cute and smart and her parents are planning to set an interesting task for her.

They prepared a tree (a connected graph without cycles) with one gift in each vertex.
Vertices are numbered 1 through N and the i-th of them contains a gift with value Gi.
A value Gi describes Valentina's happiness if she got a gift from the i-th vertex.
All gifts are wrapped so Valentina doesn't know their values.

Note that Gi could be negative and it would mean that Valentina doesn't like the gift (do you remember when your parents gave you clothes or toys not adequate to your interests?).

Let's consider the following process:
1) Valentina chooses two vertices, A and B (not necessarily distinct).
2) She unpacks all gifts on the path connecting A and B and thus she sees their values.
3) She chooses some part of the path connecting A and B. The chosen part must be connected and can't be empty (hence, it must be a path).
4) Valentina takes all gifts in the chosen part of the path and her total happiness is equal to the sum of the values of taken gifts.

Valentina is smart and for chosen A and B she will choose a part resulting in the biggest total happiness.

In order to maximize her chance to get a good bunch of gifts, parents allow her to ask Q questions, each with two numbers, A and B.
For each Valentina's question parents will tell her the answer - the maximum total happiness for chosen A and B.

They noticed that answering Valentina's questions is an interesting problem.
They want to know if you are smart enough to correctly answer all questions.

Input format
The first N+1 lines describe a tree with gifts.

The first of them contains a single integer N, the number of vertices in a tree.
The next N-1 lines contain 2 integers each, denoting two vertices connected by an edge.
The next line contains N space-separated integers, G1, G2, ..., GN.

Then, the questions are given.

One line contains a single integer Q, the number of Valentina's questions.
Finally, each of the last Q lines contains two integers A and B (1 ≤ A, B ≤ N), describing one question.

Output format
For each of the Q questions print the answer in a separate line.

Constraints
2 ≤ N ≤ 100,000
1 ≤ Q ≤ 500,000
|Gi| ≤ 10^9

SAMPLE INPUT
6
1 2
3 1
1 4
4 5
4 6
-1 2 2 -2 5 8
7
2 5
2 3
1 5
5 3
4 1
6 5
4 4

SAMPLE OUTPUT
5
3
5
5
-1
11
-2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vova has recently learned what a circulaton in a graph is. Recall the definition: let G = (V, E) be a directed graph. A circulation f is such a collection of non-negative real numbers f_e (e ∈ E), that for each vertex v ∈ V the following conservation condition holds:

$$$∑_{e ∈ \delta^{-}(v)} f_e = ∑_{e ∈ \delta^{+}(v)} f_e$$$

where \delta^{+}(v) is the set of edges that end in the vertex v, and \delta^{-}(v) is the set of edges that start in the vertex v. In other words, for each vertex the total incoming flow should be equal to the total outcoming flow.

Let a lr-circulation be such a circulation f that for each edge the condition l_e ≤ f_e ≤ r_e holds, where l_e and r_e for each edge e ∈ E are two non-negative real numbers denoting the lower and upper bounds on the value of the circulation on this edge e.

Vova can't stop thinking about applications of a new topic. Right now he thinks about the following natural question: let the graph be fixed, and each value l_e and r_e be a linear function of a real variable t:

$$$l_e(t) = a_e t + b_e r_e(t) = c_e t + d_e$$$

Note that t is the same for all edges.

Let t be chosen at random from uniform distribution on a segment [0, 1]. What is the probability of existence of lr-circulation in the graph?

Input

The first line contains two integers n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 2000).

Each of the next m lines describes edges of the graph in the format u_e, v_e, a_e, b_e, c_e, d_e (1 ≤ u_e, v_e ≤ n, -10^4 ≤ a_e, c_e ≤ 10^4, 0 ≤ b_e, d_e ≤ 10^4), where u_e and v_e are the startpoint and the endpoint of the edge e, and the remaining 4 integers describe the linear functions for the upper and lower bound of circulation.

It is guaranteed that for any t ∈ [0, 1] and for any edge e ∈ E the following condition holds 0 ≤ l_e(t) ≤ r_e(t) ≤ 10^4.

Output

Print a single real integer — the probability of existence of lr-circulation in the graph, given that t is chosen uniformly at random from the segment [0, 1]. Your answer is considered correct if its absolute difference from jury's answer is not greater than 10^{-6}.

Example

Input

3 3
1 2 0 3 -4 7
2 3 -2 5 1 6
3 1 0 4 0 4


Output

0.25

Note

In the first example the conservation condition allows only circulations with equal values f_e for all three edges. The value of circulation on the last edge should be 4 whatever t is chosen, so the probability is

$$$P(4 ∈ [3, -4t + 7]~~\&~~4 ∈ [-2t + 5, t + 6]) = 0.25$$$

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Arcady is a copywriter. His today's task is to type up an already well-designed story using his favorite text editor.

Arcady types words, punctuation signs and spaces one after another. Each letter and each sign (including line feed) requires one keyboard click in order to be printed. Moreover, when Arcady has a non-empty prefix of some word on the screen, the editor proposes a possible autocompletion for this word, more precisely one of the already printed words such that its prefix matches the currently printed prefix if this word is unique. For example, if Arcady has already printed «codeforces», «coding» and «codeforces» once again, then there will be no autocompletion attempt for «cod», but if he proceeds with «code», the editor will propose «codeforces».

With a single click Arcady can follow the editor's proposal, i.e. to transform the current prefix to it. Note that no additional symbols are printed after the autocompletion (no spaces, line feeds, etc). What is the minimum number of keyboard clicks Arcady has to perform to print the entire text, if he is not allowed to move the cursor or erase the already printed symbols?

A word here is a contiguous sequence of latin letters bordered by spaces, punctuation signs and line/text beginnings/ends. Arcady uses only lowercase letters. For example, there are 20 words in «it's well-known that tic-tac-toe is a paper-and-pencil game for two players, x and o.».

Input Specification:
The only line contains Arcady's text, consisting only of lowercase latin letters, spaces, line feeds and the following punctuation signs: «.», «,», «?», «!», «'» and «-». The total amount of symbols doesn't exceed 3·105. It's guaranteed that all lines are non-empty.

Output Specification:
Print a single integer — the minimum number of clicks.

Demo Input:
['snow affects sports such as skiing, snowboarding, and snowmachine travel.\nsnowboarding is a recreational activity and olympic and paralympic sport.\n', "'co-co-co, codeforces?!'\n", 'thun-thun-thunder, thunder, thunder\nthunder, thun-, thunder\nthun-thun-thunder, thunder\nthunder, feel the thunder\nlightning then the thunder\nthunder, feel the thunder\nlightning then the thunder\nthunder, thunder\n']

Demo Output:
['141\n', '25\n', '183\n']

Note:
In sample case one it's optimal to use autocompletion for the first instance of «snowboarding» after typing up «sn» and for the second instance of «snowboarding» after typing up «snowb». This will save 7 clicks.

In sample case two it doesn't matter whether to use autocompletion or not.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kuro and Walking Route

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kuro is living in a country called Uberland, consisting of $n$ towns, numbered from $1$ to $n$, and $n - 1$ bidirectional roads connecting these towns. It is possible to reach each town from any other. Each road connects two towns $a$ and $b$. Kuro loves walking and he is planning to take a walking marathon, in which he will choose a pair of towns $(u, v)$ ($u \neq v$) and walk from $u$ using the shortest path to $v$ (note that $(u, v)$ is considered to be different from $(v, u)$).

Oddly, there are 2 special towns in Uberland named Flowrisa (denoted with the index $x$) and Beetopia (denoted with the index $y$). Flowrisa is a town where there are many strong-scent flowers, and Beetopia is another town where many bees live. In particular, Kuro will avoid any pair of towns $(u, v)$ if on the path from $u$ to $v$, he reaches Beetopia after he reached Flowrisa, since the bees will be attracted with the flower smell on Kuro’s body and sting him.

Kuro wants to know how many pair of city $(u, v)$ he can take as his route. Since he’s not really bright, he asked you to help him with this problem.

Input Specification:
The first line contains three integers $n$, $x$ and $y$ ($1 \leq n \leq 3 \cdot 10^5$, $1 \leq x, y \leq n$, $x \ne y$) - the number of towns, index of the town Flowrisa and index of the town Beetopia, respectively.

$n - 1$ lines follow, each line contains two integers $a$ and $b$ ($1 \leq a, b \leq n$, $a \ne b$), describes a road connecting two towns $a$ and $b$.

It is guaranteed that from each town, we can reach every other town in the city using the given roads. That is, the given map of towns and roads is a tree.

Output Specification:
A single integer resembles the number of pair of towns $(u, v)$ that Kuro can use as his walking route.

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

Demo Output:
['5', '4']

Note:
On the first example, Kuro can choose these pairs: 
 -  $(1, 2)$: his route would be $1 \rightarrow 2$, -  $(2, 3)$: his route would be $2 \rightarrow 3$, -  $(3, 2)$: his route would be $3 \rightarrow 2$, -  $(2, 1)$: his route would be $2 \rightarrow 1$, -  $(3, 1)$: his route would be $3 \rightarrow 2 \rightarrow 1$. 
Kuro can't choose pair $(1, 3)$ since his walking route would be $1 \rightarrow 2 \rightarrow 3$, in which Kuro visits town $1$ (Flowrisa) and then visits town $3$ (Beetopia), which is not allowed (note that pair $(3, 1)$ is still allowed because although Kuro visited Flowrisa and Beetopia, he did not visit them in that order).

On the second example, Kuro can choose the following pairs: 
 -  $(1, 2)$: his route would be $1 \rightarrow 2$, -  $(2, 1)$: his route would be $2 \rightarrow 1$, -  $(3, 2)$: his route would be $3 \rightarrow 1 \rightarrow 2$, -  $(3, 1)$: his route would be $3 \rightarrow 1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a linked list of N nodes. The task is to reverse this list.
Example 1:
Input:
LinkedList: 1->2->3->4->5->6
Output: 6 5 4 3 2 1
Explanation: After reversing the list, 
elements are 6->5->4->3->2->1.
Example 2:
Input:
LinkedList: 2->7->8->9->10
Output: 10 9 8 7 2
Explanation: After reversing the list,
elements are 10->9->8->7->2.
Your Task:
The task is to complete the function reverseList() with head reference as the only argument and should return new head after reversing the list.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sort array by last character

Complete the function to sort a given array or list by last character of elements.

```if-not:haskell
Element can be an integer or a string.
```

### Example:

```
['acvd', 'bcc']  -->  ['bcc', 'acvd']
```

The last characters of the strings are `d` and `c`. As `c` comes before `d`, sorting by last character will give `['bcc', 'acvd']`.

If two elements don't differ in the last character, then they should be sorted by the order they come in the array.

```if:haskell
Elements will not be empty (but the list may be).
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You took a peek on Thanos wearing Infinity Gauntlet. In the Gauntlet there is a place for six Infinity Gems:
 -  the Power Gem of purple color, -  the Time Gem of green color, -  the Space Gem of blue color, -  the Soul Gem of orange color, -  the Reality Gem of red color, -  the Mind Gem of yellow color. 
Using colors of Gems you saw in the Gauntlet determine the names of absent Gems.

Input Specification:
In the first line of input there is one integer $n$ ($0 \le n \le 6$) — the number of Gems in Infinity Gauntlet.

In next $n$ lines there are colors of Gems you saw. Words used for colors are: purple, green, blue, orange, red, yellow. It is guaranteed that all the colors are distinct. All colors are given in lowercase English letters.

Output Specification:
In the first line output one integer $m$ ($0 \le m \le 6$) — the number of absent Gems.

Then in $m$ lines print the names of absent Gems, each on its own line. Words used for names are: Power, Time, Space, Soul, Reality, Mind. Names can be printed in any order. Keep the first letter uppercase, others lowercase.

Demo Input:
['4\nred\npurple\nyellow\norange\n', '0\n']

Demo Output:
['2\nSpace\nTime\n', '6\nTime\nMind\nSoul\nPower\nReality\nSpace\n']

Note:
In the first sample Thanos already has Reality, Power, Mind and Soul Gems, so he needs two more: Time and Space.

In the second sample Thanos doesn't have any Gems, so he needs all six.

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