vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Bob is completing a true/false worksheet, consisting of a list of $n$ problems where each answer is either “true” or “false”. The problems are numbered from $1$ to $n$. They are too hard for Bob, so the TA, Alice, has given Bob $m$ hints. For each hint $i$, Alice gives Bob an (inclusive) range of questions $[l_ i, r_ i]$, and tells him either “all answers in the range are the same” (in other words, either all are “true”, or all are “false”); or “not all of the answers in the range are the same.” Help Bob count how many different answer sequences satisfy the given hints. Since this number may be huge, print the answer modulo $10^9+7$.

-----Input-----
The first line of the input contains two space-separated integers $n$ and $m$ $(1 \le n \le 5000, 1 \le m \le 1000000)$, the number of problems and number of hints, respectively. The next $m$ lines each encode a hint, and contain two space-separated integers $l_ i$ and $r_ i$ $(1\leq l_ i \leq r_ i\leq n)$ followed by either the word same, if all answers in the range are the same, or different, if all answers in the range are not the same (i.e., at least one answer is “true” and at least one other answer is “false”).

-----Output-----
Print the number of different answer sequences satisfying all the hints, modulo $10^9+7$.

-----Sample Explanation-----
In the first sample, the four possible sequences consistent with the hints are 00000, 10000, 01111, and 11111 where 0 stands for a “false” answer and 1 stands for a “true” answer. In the second sample, the third hint conflicts with the first two hints, so no answer sequence exists consistent with all hints.

-----Examples-----
Sample Input:
5 2
2 4 same
3 5 same
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $a$ and $m$. Calculate the number of integers $x$ such that $0 \le x < m$ and $\gcd(a, m) = \gcd(a + x, m)$.

Note: $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$.


-----Input-----

The first line contains the single integer $T$ ($1 \le T \le 50$) — the number of test cases.

Next $T$ lines contain test cases — one per line. Each line contains two integers $a$ and $m$ ($1 \le a < m \le 10^{10}$).


-----Output-----

Print $T$ integers — one per test case. For each test case print the number of appropriate $x$-s.


-----Example-----
Input
3
4 9
5 10
42 9999999967

Output
6
1
9999999966



-----Note-----

In the first test case appropriate $x$-s are $[0, 1, 3, 4, 6, 7]$.

In the second test case the only appropriate $x$ is $0$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera is a little boy. Yesterday he got a huge Math hometask at school, so Valera didn't have enough time to properly learn the English alphabet for his English lesson. Unfortunately, the English teacher decided to have a test on alphabet today. At the test Valera got a square piece of squared paper. The length of the side equals *n* squares (*n* is an odd number) and each unit square contains some small letter of the English alphabet.

Valera needs to know if the letters written on the square piece of paper form letter "X". Valera's teacher thinks that the letters on the piece of paper form an "X", if:
 -  on both diagonals of the square paper all letters are the same; -  all other squares of the paper (they are not on the diagonals) contain the same letter that is different from the letters on the diagonals. 
Help Valera, write the program that completes the described task for him.

Input Specification:
The first line contains integer *n* (3<=≤<=*n*<=&lt;<=300; *n* is odd). Each of the next *n* lines contains *n* small English letters — the description of Valera's paper.

Output Specification:
Print string "YES", if the letters on the paper form letter "X". Otherwise, print string "NO". Print the strings without quotes.

Demo Input:
['5\nxooox\noxoxo\nsoxoo\noxoxo\nxooox\n', '3\nwsw\nsws\nwsw\n', '3\nxpx\npxp\nxpe\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given a string and your task will be to return the length of the longest prefix that is also a suffix. A prefix is the start of a string while the suffix is the end of a string.  For instance, the prefixes of the string `"abcd"` are `["a","ab","abc"]`. The suffixes are `["bcd", "cd", "d"]`. You should not overlap the prefix and suffix.

```Haskell
for example:
solve("abcd") = 0, because no prefix == suffix. 
solve("abcda") = 1, because the longest prefix which == suffix is "a".
solve("abcdabc") = 3. Longest prefix which == suffix is "abc".
solve("aaaa") = 2. Longest prefix which == suffix is "aa". You should not overlap the prefix and suffix
solve("aa") = 1. You should not overlap the prefix and suffix.
solve("a") = 0. You should not overlap the prefix and suffix.
```

All strings will be lowercase and string lengths are `1 <= length <= 500`

More examples in test cases. Good luck!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are some websites that are accessible through several different addresses. For example, for a long time Codeforces was accessible with two hostnames codeforces.com and codeforces.ru.

You are given a list of page addresses being queried. For simplicity we consider all addresses to have the form http://&lt;hostname&gt;[/&lt;path&gt;], where:
 -  &lt;hostname&gt; — server name (consists of words and maybe some dots separating them), -  /&lt;path&gt; — optional part, where &lt;path&gt; consists of words separated by slashes. 
We consider two &lt;hostname&gt; to correspond to one website if for each query to the first &lt;hostname&gt; there will be exactly the same query to the second one and vice versa — for each query to the second &lt;hostname&gt; there will be the same query to the first one. Take a look at the samples for further clarifications.

Your goal is to determine the groups of server names that correspond to one website. Ignore groups consisting of the only server name.

Please note, that according to the above definition queries http://&lt;hostname&gt; and http://&lt;hostname&gt;/ are different.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=100<=000) — the number of page queries. Then follow *n* lines each containing exactly one address. Each address is of the form http://&lt;hostname&gt;[/&lt;path&gt;], where:
 -  &lt;hostname&gt; consists of lowercase English letters and dots, there are no two consecutive dots, &lt;hostname&gt; doesn't start or finish with a dot. The length of &lt;hostname&gt; is positive and doesn't exceed 20. -  &lt;path&gt; consists of lowercase English letters, dots and slashes. There are no two consecutive slashes, &lt;path&gt; doesn't start with a slash and its length doesn't exceed 20. 
Addresses are not guaranteed to be distinct.

Output Specification:
First print *k* — the number of groups of server names that correspond to one website. You should count only groups of size greater than one.

Next *k* lines should contain the description of groups, one group per line. For each group print all server names separated by a single space. You are allowed to print both groups and names inside any group in arbitrary order.

Demo Input:
['10\nhttp://abacaba.ru/test\nhttp://abacaba.ru/\nhttp://abacaba.com\nhttp://abacaba.com/test\nhttp://abacaba.de/\nhttp://abacaba.ru/test\nhttp://abacaba.de/test\nhttp://abacaba.com/\nhttp://abacaba.com/t\nhttp://abacaba.com/test\n', '14\nhttp://c\nhttp://ccc.bbbb/aba..b\nhttp://cba.com\nhttp://a.c/aba..b/a\nhttp://abc/\nhttp://a.c/\nhttp://ccc.bbbb\nhttp://ab.ac.bc.aa/\nhttp://a.a.a/\nhttp://ccc.bbbb/\nhttp://cba.com/\nhttp://cba.com/aba..b\nhttp://a.a.a/aba..b/a\nhttp://abc/aba..b/a\n']

Demo Output:
['1\nhttp://abacaba.de http://abacaba.ru \n', '2\nhttp://cba.com http://ccc.bbbb \nhttp://a.a.a http://a.c http://abc \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kana was just an ordinary high school girl before a talent scout discovered her. Then, she became an idol. But different from the stereotype, she is also a gameholic. 

One day Kana gets interested in a new adventure game called Dragon Quest. In this game, her quest is to beat a dragon.

<image>

The dragon has a hit point of x initially. When its hit point goes to 0 or under 0, it will be defeated. In order to defeat the dragon, Kana can cast the two following types of spells. 

  * Void Absorption

Assume that the dragon's current hit point is h, after casting this spell its hit point will become \left⌊ h/2 \right⌋ + 10. Here \left⌊ h/2 \right⌋ denotes h divided by two, rounded down.

  * Lightning Strike

This spell will decrease the dragon's hit point by 10. Assume that the dragon's current hit point is h, after casting this spell its hit point will be lowered to h-10.




Due to some reasons Kana can only cast no more than n Void Absorptions and m Lightning Strikes. She can cast the spells in any order and doesn't have to cast all the spells. Kana isn't good at math, so you are going to help her to find out whether it is possible to defeat the dragon.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The next t lines describe test cases. For each test case the only line contains three integers x, n, m (1≤ x ≤ 10^5, 0≤ n,m≤30) — the dragon's intitial hit point, the maximum number of Void Absorptions and Lightning Strikes Kana can cast respectively.

Output

If it is possible to defeat the dragon, print "YES" (without quotes). Otherwise, print "NO" (without quotes).

You can print each letter in any case (upper or lower).

Example

Input


7
100 3 4
189 3 4
64 2 3
63 2 3
30 27 7
10 9 1
69117 21 2


Output


YES
NO
NO
YES
YES
YES
YES

Note

One possible casting sequence of the first test case is shown below:

  * Void Absorption \left⌊ 100/2 \right⌋ + 10=60.
  * Lightning Strike 60-10=50.
  * Void Absorption \left⌊ 50/2 \right⌋ + 10=35.
  * Void Absorption \left⌊ 35/2 \right⌋ + 10=27.
  * Lightning Strike 27-10=17.
  * Lightning Strike 17-10=7.
  * Lightning Strike 7-10=-3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, the Fair Nut has written $k$ strings of length $n$, consisting of letters "a" and "b". He calculated $c$ — the number of strings that are prefixes of at least one of the written strings. Every string was counted only one time.

Then, he lost his sheet with strings. He remembers that all written strings were lexicographically not smaller than string $s$ and not bigger than string $t$. He is interested: what is the maximum value of $c$ that he could get.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds: $a$ is a prefix of $b$, but $a \ne b$; in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 5 \cdot 10^5$, $1 \leq k \leq 10^9$).

The second line contains a string $s$ ($|s| = n$) — the string consisting of letters "a" and "b.

The third line contains a string $t$ ($|t| = n$) — the string consisting of letters "a" and "b.

It is guaranteed that string $s$ is lexicographically not bigger than $t$.


-----Output-----

Print one number — maximal value of $c$.


-----Examples-----
Input
2 4
aa
bb

Output
6

Input
3 3
aba
bba

Output
8

Input
4 5
abbb
baaa

Output
8



-----Note-----

In the first example, Nut could write strings "aa", "ab", "ba", "bb". These $4$ strings are prefixes of at least one of the written strings, as well as "a" and "b". Totally, $6$ strings.

In the second example, Nut could write strings "aba", "baa", "bba".

In the third example, there are only two different strings that Nut could write. If both of them are written, $c=8$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fennec and Snuke are playing a board game.
On the board, there are N cells numbered 1 through N, and N-1 roads, each connecting two cells. Cell a_i is adjacent to Cell b_i through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.
Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored.
Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell.
More specifically, each player performs the following action in her/his turn:
 - Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.
 - Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.
A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 1 \leq a_i, b_i \leq N
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 b_1
:
a_{N-1} b_{N-1}

-----Output-----
If Fennec wins, print Fennec; if Snuke wins, print Snuke.

-----Sample Input-----
7
3 6
1 2
3 1
7 4
5 7
1 4

-----Sample Output-----
Fennec

For example, if Fennec first paints Cell 2 black, she will win regardless of Snuke's moves.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$N$ points are placed in the coordinate plane.

Write a program which calculates in how many ways a right triangle can be formed by three of the given points. A right triangle is one in which one of the angles is $90$ degrees.

-----Input-----
The first line of input contains an integer $N$ ($3 \le N \le 1500$), the number of points.

Each of the following $N$ lines contains the coordinates of one point, two integers separated by a space. The coordinates will be between $-10^9$ and $10^9$.

No two points will be located at the same coordinates.

-----Output-----
Output the number of right triangles.

-----Examples-----
Sample Input 1:
3
4 2
2 1
1 3
Sample Output 1:
1

Sample Input 2:
4
5 0
2 6
8 6
5 7
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers A and B as the input. Output the value of A + B.
However, if A + B is 10 or greater, output error instead.

-----Constraints-----
 - A and B are integers.
 - 1 ≤ A, B ≤ 9

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
If A + B is 10 or greater, print the string error (case-sensitive); otherwise, print the value of A + B.

-----Sample Input-----
6 3

-----Sample Output-----
9


Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your friend Nick needs your help with a hard problem that he came across in real life. Nick has a loo roll of length $\ell $ centimetres in his bathroom. Every time he visits the toilet, he uses exactly $n$ centimetres of loo roll. When the roll runs out, Nick always goes to the store and buys a new one of length $\ell $ directly afterwards. However, sometimes the roll runs out even though Nick still needs a non-zero amount of paper. Let us call such an event a crisis. 

Nick has a clever way of preventing crises from happening: he uses a backup roll. The backup roll is another roll of length $\ell $ that is hidden somewhere in the bathroom, and when the regular roll runs out even though Nick still needs more paper, he will take that amount from the backup roll. Then he will replace the regular roll directly after the visit.

As you can imagine, this makes crises much less frequent. But still, the backup roll will also slowly run out, and eventually a crisis might still happen. So to generalize this, Nick wants to use several layers of backup rolls. First he will take paper from roll number $1$ (the regular roll), if it runs out he will take from roll number $2$, then if roll $2$ runs out from roll number $3$, and so on all the way up to roll number $k$. After each visit, all the rolls that have run out will be replaced. Nick managed to prove that if he picks a large enough number $k$, he can actually make it so that crises never happen! Your task is to find the smallest such number $k$.

-----Input-----
The input consists of a single line containing the two integers $\ell $ and $n$ ($1 \leq n \leq \ell \leq 10^{10}$).

-----Output-----
Output the smallest integer $k$ such that crises will never happen when using $k$ layers of rolls (including the regular roll).

-----Examples-----
Sample Input:
31 6
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja loves integer sequences very much. He especially likes stairs.

Sequence a_1, a_2, ..., a_{|}a| (|a| is the length of the sequence) is stairs if there is such index i (1 ≤ i ≤ |a|), that the following condition is met: a_1 < a_2 < ... < a_{i} - 1 < a_{i} > a_{i} + 1 > ... > a_{|}a| - 1 > a_{|}a|.

For example, sequences [1, 2, 3, 2] and [4, 2] are stairs and sequence [3, 1, 2] isn't.

Sereja has m cards with numbers. He wants to put some cards on the table in a row to get a stair sequence. What maximum number of cards can he put on the table?


-----Input-----

The first line contains integer m (1 ≤ m ≤ 10^5) — the number of Sereja's cards. The second line contains m integers b_{i} (1 ≤ b_{i} ≤ 5000) — the numbers on the Sereja's cards.


-----Output-----

In the first line print the number of cards you can put on the table. In the second line print the resulting stairs.


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

Output
5
5 4 3 2 1

Input
6
1 1 2 2 3 3

Output
5
1 2 3 2 1

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

The input contains two integers a1, a2 (0 ≤ ai ≤ 109), separated by a single space.

Output

Output a single integer.

Examples

Input

3 14


Output

44


Input

27 12


Output

48


Input

100 200


Output

102

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
String diversity is the number of symbols that occur in the string at least once. Diversity of s will be denoted by d(s). For example , d("aaa")=1, d("abacaba")=3.

Given a string s, consisting of lowercase Latin letters. Consider all its substrings. Obviously, any substring diversity is a number from 1 to d(s). Find statistics about substrings diversity: for each k from 1 to d(s), find how many substrings of s has a diversity of exactly k.

Input

The input consists of a single line containing s. It contains only lowercase Latin letters, the length of s is from 1 to 3·105.

Output

Print to the first line the value d(s). Print sequence t1, t2, ..., td(s) to the following lines, where ti is the number of substrings of s having diversity of exactly i.

Examples

Input

abca


Output

3
4
3
3


Input

aabacaabbad


Output

4
14
19
28
5

Note

Consider the first example.

We denote by s(i, j) a substring of "abca" with the indices in the segment [i, j].

  * s(1, 1) =  "a", d("a") = 1
  * s(2, 2) =  "b", d("b") = 1
  * s(3, 3) =  "c", d("c") = 1
  * s(4, 4) =  "a", d("a") = 1
  * s(1, 2) =  "ab", d("ab") = 2
  * s(2, 3) =  "bc", d("bc") = 2
  * s(3, 4) =  "ca", d("ca") = 2
  * s(1, 3) =  "abc", d("abc") = 3
  * s(2, 4) =  "bca", d("bca") = 3
  * s(1, 4) =  "abca", d("abca") = 3



Total number of substring with diversity 1 is 4, with diversity 2 equals 3, 3 diversity is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a linked list of N nodes, sorted in ascending order based on the absolute values of its data,i.e. negative values are considered as positive ones. Sort the linked list in ascending order according to the actual values, and consider negative numbers as negative and positive numbers as positive.
Example 1:  
Input: 
List: 1, -2, -3, 4, -5
Output: 
List: -5, -3, -2, 1, 4
Explanation: 
Actual sorted order of {1, -2, -3, 4, -5}
is {-5, -3, -2, 1, 4}
 
Example 2:  
Input: 
List: 5, -10
Output: 
List: -10, 5
Explanation:
Actual sorted order of {5, -10}
is {-10, 5}
 
Your Task:
You don't need to read or print anything. Your Task is to complete the function sortList() which takes the head of the Linked List as input parameter and sort the list in ascending order and return the head pointer of the sorted list.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
Constraints
1 ≤  N  ≤ 10^5
-10^5 ≤  node.data ≤ 10^5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Miraya and her best Alice friend are now ending their studies and they are willing to work together in a software company, but before this Alice will be tested by the Miraya through the following procedure,
Miraya is obviously Computer Science person while her best friend belongs to Arts. However, as Miraya didn't want to lose contact with her, she decided to mix Arts and Computer-Science one last time and amaze her friend with Computer-Science, so she could have a geek coding partner.

To amaze her, Miraya selected a natural number N, which she presented to her friend Alice.

Miraya: "So, Alice, as you can see, we have a Natural Number N, yes? The first thing you have to do is ,If you write down the first N natural numbers on a paper you will get a sequence of distinct numbers. You can denote them as 
{x1,x2,x3,…..,xn} a sequence of N distinct integers, which is also a  permutation of first N natural numbers."

Miraya: “Now Alice we have a permutation of first N natural numbers. You can select any permutation of the aforesaid permutation to find out an optimal permutation of numbers. A permutation is said to be optimal if it maximizes the summation of absolute differences of all the consecutive elements of the permutation when written as it is on the paper.”

But Alice is very weak in solving such kind of problems. So she needs your help to get the desired maximum value from the Optimal Permutation. If it becomes possible for Alice then, they will be working together in the same software company. 

Constraints:

1 ≤ T ≤ 10^3

1 ≤ N ≤ (2 x 10^5)

Input:

The first line of the input contains an integer T denoting the number of test cases.
then each test case contains a single integer N.

Output:

For each test case output the required answer in separate line to help Alice.

SAMPLE INPUT
2
2
7

SAMPLE OUTPUT
1
23

Explanation

In Test-case # 1 for n=2 the possible sequences are {1,2} & {2,1} and both yielding the same result i.e. abs(1-2) = 1.

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