vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
It's been a hard time for Baahubali in mathematics. Yet another challenge from Kattappa. 
Baahubali is given 5 integers in the range 0-50, he needs to figure out if there is a way to obtain a result 23 from those numbers if only operations allowed between any two integers are +, -, *

Final operated result should be of the form
((((num1 op1 num2) op2 num3) op3 num4) op4 num5)

Input

First Line, number of test cases 1 ≤ t ≤ 100

Each test case has 5 integers in the range  0 to 50 (inclusive)

Output

For each test case, print "YES" (without quotes) if 23 is obtainable else "NO" (without quotes) 

SAMPLE INPUT
2
1 1 1 1 1
1 2 3 4 5

SAMPLE OUTPUT
NO
YES

Explanation

Case 1 : There is no way to get 23. Hence NO

case 2 :  1 + 2 * 5 + 3 * 4 = 23. Hence YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a sequence of N integers: x=(x_0,x_1,\cdots,x_{N-1}). Initially, x_i=0 for each i (0 \leq i \leq N-1).

Snuke will perform the following operation exactly M times:

* Choose two distinct indices i, j (0 \leq i,j \leq N-1,\ i \neq j). Then, replace x_i with x_i+2 and x_j with x_j+1.



Find the number of different sequences that can result after M operations. Since it can be enormous, compute the count modulo 998244353.

Constraints

* 2 \leq N \leq 10^6
* 1 \leq M \leq 5 \times 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M


Output

Print the number of different sequences that can result after M operations, modulo 998244353.

Examples

Input

2 2


Output

3


Input

3 2


Output

19


Input

10 10


Output

211428932


Input

100000 50000


Output

3463133

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s consisting of lowercase English letters. Extract all the characters in the odd-indexed positions and print the string obtained by concatenating them. Here, the leftmost character is assigned the index 1.

-----Constraints-----
 - Each character in s is a lowercase English letter.
 - 1≤|s|≤10^5

-----Input-----
The input is given from Standard Input in the following format:
s

-----Output-----
Print the string obtained by concatenating all the characters in the odd-numbered positions.

-----Sample Input-----
atcoder

-----Sample Output-----
acdr

Extract the first character a, the third character c, the fifth character d and the seventh character r to obtain acdr.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a non-empty string *s* consisting of lowercase letters. Find the number of pairs of non-overlapping palindromic substrings of this string.

In a more formal way, you have to find the quantity of tuples (*a*,<=*b*,<=*x*,<=*y*) such that 1<=≤<=*a*<=≤<=*b*<=&lt;<=*x*<=≤<=*y*<=≤<=|*s*| and substrings *s*[*a*... *b*], *s*[*x*... *y*] are palindromes.

A palindrome is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.

A substring *s*[*i*... *j*] (1<=≤<=*i*<=≤<=*j*<=≤<=|*s*|) of string *s* = *s*1*s*2... *s*|*s*| is a string *s**i**s**i*<=+<=1... *s**j*. For example, substring *s*[2...4] of string *s* = "abacaba" equals "bac".

Input Specification:
The first line of input contains a non-empty string *s* which consists of lowercase letters ('a'...'z'), *s* contains at most 2000 characters.

Output Specification:
Output a single number — the quantity of pairs of non-overlapping palindromic substrings of *s*.

Please do not use the %lld format specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d format specifier.

Demo Input:
['aa\n', 'aaa\n', 'abacaba\n']

Demo Output:
['1\n', '5\n', '36\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Allen is playing Number Clicker on his phone.

He starts with an integer u on the screen. Every second, he can press one of 3 buttons.

  1. Turn u → u+1 \pmod{p}. 
  2. Turn u → u+p-1 \pmod{p}. 
  3. Turn u → u^{p-2} \pmod{p}. 



Allen wants to press at most 200 buttons and end up with v on the screen. Help him!

Input

The first line of the input contains 3 positive integers: u, v, p (0 ≤ u, v ≤ p-1, 3 ≤ p ≤ 10^9 + 9). p is guaranteed to be prime.

Output

On the first line, print a single integer ℓ, the number of button presses. On the second line, print integers c_1, ..., c_ℓ, the button presses. For 1 ≤ i ≤ ℓ, 1 ≤ c_i ≤ 3.

We can show that the answer always exists.

Examples

Input

1 3 5


Output

2
1 1


Input

3 2 5


Output

1
3

Note

In the first example the integer on the screen changes as 1 → 2 → 3.

In the second example the integer on the screen changes as 3 → 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

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

-----Sample Output:-----
1
12
34
123
456
789
1234
5678
9101112
13141516

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Daniel has a string s, consisting of lowercase English letters and period signs (characters '.'). Let's define the operation of replacement as the following sequence of steps: find a substring ".." (two consecutive periods) in string s, of all occurrences of the substring let's choose the first one, and replace this substring with string ".". In other words, during the replacement operation, the first two consecutive periods are replaced by one. If string s contains no two consecutive periods, then nothing happens.

Let's define f(s) as the minimum number of operations of replacement to perform, so that the string does not have any two consecutive periods left.

You need to process m queries, the i-th results in that the character at position x_{i} (1 ≤ x_{i} ≤ n) of string s is assigned value c_{i}. After each operation you have to calculate and output the value of f(s).

Help Daniel to process all queries.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 300 000) the length of the string and the number of queries.

The second line contains string s, consisting of n lowercase English letters and period signs.

The following m lines contain the descriptions of queries. The i-th line contains integer x_{i} and c_{i} (1 ≤ x_{i} ≤ n, c_{i} — a lowercas English letter or a period sign), describing the query of assigning symbol c_{i} to position x_{i}.


-----Output-----

Print m numbers, one per line, the i-th of these numbers must be equal to the value of f(s) after performing the i-th assignment.


-----Examples-----
Input
10 3
.b..bz....
1 h
3 c
9 f

Output
4
3
1

Input
4 4
.cc.
2 .
3 .
2 a
1 a

Output
1
3
1
1



-----Note-----

Note to the first sample test (replaced periods are enclosed in square brackets).

The original string is ".b..bz....". after the first query f(hb..bz....) = 4    ("hb[..]bz...."  →  "hb.bz[..].."  →  "hb.bz[..]."  →  "hb.bz[..]"  →  "hb.bz.") after the second query f(hbс.bz....) = 3    ("hbс.bz[..].."  →  "hbс.bz[..]."  →  "hbс.bz[..]"  →  "hbс.bz.") after the third query f(hbс.bz..f.) = 1    ("hbс.bz[..]f."  →  "hbс.bz.f.")

Note to the second sample test.

The original string is ".cc.". after the first query: f(..c.) = 1    ("[..]c."  →  ".c.") after the second query: f(....) = 3    ("[..].."  →  "[..]."  →  "[..]"  →  ".") after the third query: f(.a..) = 1    (".a[..]"  →  ".a.") after the fourth query: f(aa..) = 1    ("aa[..]"  →  "aa.")

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored with easy solutions of this problem, and he has come up with the following extravagant algorithm.

Let's consider that initially array contains *n* numbers from 1 to *n* and the number *i* is located in the cell with the index 2*i*<=-<=1 (Indices are numbered starting from one) and other cells of the array are empty. Each step Dima selects a non-empty array cell with the maximum index and moves the number written in it to the nearest empty cell to the left of the selected one. The process continues until all *n* numbers will appear in the first *n* cells of the array. For example if *n*<==<=4, the array is changing as follows:

You have to write a program that allows you to determine what number will be in the cell with index *x* (1<=≤<=*x*<=≤<=*n*) after Dima's algorithm finishes.

Input Specification:
The first line contains two integers *n* and *q* (1<=≤<=*n*<=≤<=1018, 1<=≤<=*q*<=≤<=200<=000), the number of elements in the array and the number of queries for which it is needed to find the answer.

Next *q* lines contain integers *x**i* (1<=≤<=*x**i*<=≤<=*n*), the indices of cells for which it is necessary to output their content after Dima's algorithm finishes.

Output Specification:
For each of *q* queries output one integer number, the value that will appear in the corresponding array cell after Dima's algorithm finishes.

Demo Input:
['4 3\n2\n3\n4\n', '13 4\n10\n5\n4\n8\n']

Demo Output:
['3\n2\n4\n', '13\n3\n8\n9\n']

Note:
The first example is shown in the picture.

In the second example the final array is [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Om Nom and Necklace

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Om Nom found a thread with *n* beads of different colors. He decided to cut the first several beads from this thread to make a bead necklace and present it to his girlfriend Om Nelly.

Om Nom knows that his girlfriend loves beautiful patterns. That's why he wants the beads on the necklace to form a regular pattern. A sequence of beads *S* is regular if it can be represented as *S*<==<=*A*<=+<=*B*<=+<=*A*<=+<=*B*<=+<=*A*<=+<=...<=+<=*A*<=+<=*B*<=+<=*A*, where *A* and *B* are some bead sequences, "<=+<=" is the concatenation of sequences, there are exactly 2*k*<=+<=1 summands in this sum, among which there are *k*<=+<=1 "*A*" summands and *k* "*B*" summands that follow in alternating order. Om Nelly knows that her friend is an eager mathematician, so she doesn't mind if *A* or *B* is an empty sequence.

Help Om Nom determine in which ways he can cut off the first several beads from the found thread (at least one; probably, all) so that they form a regular pattern. When Om Nom cuts off the beads, he doesn't change their order.

Input Specification:
The first line contains two integers *n*, *k* (1<=≤<=*n*,<=*k*<=≤<=1<=000<=000) — the number of beads on the thread that Om Nom found and number *k* from the definition of the regular sequence above.

The second line contains the sequence of *n* lowercase Latin letters that represent the colors of the beads. Each color corresponds to a single letter.

Output Specification:
Print a string consisting of *n* zeroes and ones. Position *i* (1<=≤<=*i*<=≤<=*n*) must contain either number one if the first *i* beads on the thread form a regular sequence, or a zero otherwise.

Demo Input:
['7 2\nbcabcab\n', '21 2\nababaababaababaababaa\n']

Demo Output:
['0000011', '000110000111111000011']

Note:
In the first sample test a regular sequence is both a sequence of the first 6 beads (we can take *A* = "", *B* = "bca"), and a sequence of the first 7 beads (we can take *A* = "b", *B* = "ca").

In the second sample test, for example, a sequence of the first 13 beads is regular, if we take *A* = "aba", *B* = "ba".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarpus has a hobby — he develops an unusual social network. His work is almost completed, and there is only one more module to implement — the module which determines friends. Oh yes, in this social network one won't have to add friends manually! Pairs of friends are deduced in the following way. Let's assume that user A sent user B a message at time t1, and user B sent user A a message at time t2. If 0 < t2 - t1 ≤ d, then user B's message was an answer to user A's one. Users A and B are considered to be friends if A answered at least one B's message or B answered at least one A's message.

You are given the log of messages in chronological order and a number d. Find all pairs of users who will be considered to be friends.

Input

The first line of the input contains two integers n and d (1 ≤ n, d ≤ 1000). The next n lines contain the messages log. The i-th line contains one line of the log formatted as "Ai Bi ti" (without the quotes), which means that user Ai sent a message to user Bi at time ti (1 ≤ i ≤ n). Ai and Bi are non-empty strings at most 20 characters long, consisting of lowercase letters ('a' ... 'z'), and ti is an integer (0 ≤ ti ≤ 10000). It is guaranteed that the lines are given in non-decreasing order of ti's and that no user sent a message to himself. The elements in the lines are separated by single spaces.

Output

In the first line print integer k — the number of pairs of friends. In the next k lines print pairs of friends as "Ai Bi" (without the quotes). You can print users in pairs and the pairs themselves in any order. Each pair must be printed exactly once.

Examples

Input

4 1
vasya petya 1
petya vasya 2
anya ivan 2
ivan anya 4


Output

1
petya vasya


Input

1 1000
a b 0


Output

0

Note

In the first sample test case Vasya and Petya are friends because their messages' sending times are one second apart. Anya and Ivan are not, because their messages' sending times differ by more than one second.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A number K$K$ is said to be magical if it can be represented as a power of 2 only.That is K$K$=2x$2^{x}$ for some natural number x$x$. 
Given a string of digits S$S$ of length N$N$, Let P be a valid arrangement of S.
By valid arrangement we mean that it should not have any leading zeroes.
Find the sum of all such distinct Pi's, which, when treated as a number is magical.
Two arrangements are said to be distinct, if there is atleast one index where they differ. 
As the sum can be very large, print the sum modulo 109+7$10^{9}+7$.

-----Input:-----
-The first line of the input contains a single integer T$T$ denoting the number of test cases. 
-Only line of each test case contains a string S$S$ of length N$N$, consisting only of digits between 0 to 9.

-----Output:-----
For each test case, print a single integer denoting the sum of all such magical Pi′s$Pi's$ modulo 109+7$10^{9}+7$.
If no such Pi$Pi$ exists print "-1".

-----Constraints-----
- 1≤T≤1000$1 \leq T \leq 1000$
- 2≤N≤1000$2 \leq N \leq 1000$
- String only consists of digits between 0 to 9, both inclusive.

-----Subtasks-----
- 10 points : 1≤N≤5$1 \leq N \leq 5$
- 40 points : 1≤N≤100$1 \leq N \leq 100$
- 50 points : Original Constraints

-----Sample Input:-----
2
35566

31

-----Sample Output:-----
65536

-1

-----EXPLANATION:-----
Only arrangement is 65536.
No arrangement of 31 gives us a power of two.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luka is bored in chemistry class yet again. This time, he’s playing with intelligent bacteria. He has arranged his $K$ bacteria on a rectangular board divided in $N$ rows, labelled with numbers from $1$ to $N$ starting from the top, and $M$ columns, labelled with numbers from $1$ to $M$ starting from the left.

Each bacterium begins its adventure in a certain cell, facing one of the four neighbouring cells, and carries out the following actions every second:
 - Reads the number $X$ dedicated to that bacterium in the current cell.
 - Turns $90$ degrees clockwise, $X$ times.
 - If it is facing a cell outside the board, it turns $180$ degrees.
 - Finally, it moves to the cell that it is facing.

Luka has placed a trap in one cell. The trap will activate and kill the bacteria as soon as they all step on that cell in the same second.

Since Luka only has two hours of chemistry class today, help him determine how long the game will last, in seconds.

-----Input-----
The first line of input contains the positive integers $N$ ($3 \leq N \leq 50$), $M$ ($3 \leq M \leq 50$), and $K$ ($1 \leq K \leq 5$).

The second line of input contains the positive integers $X$ and $Y$, the row and column where Luka has placed the trap.

The remainder of the input consists of bacteria descriptions, for each bacterium $i$ from $1$ to $K$:
 - two positive integers $X_ i$, $Y_ i$ – the row and column of the starting cell of bacterium $i$, and the character $C_ i$ representing the starting direction that the bacterium is facing ($U$ – up, $R$ – right, $D$ – down, $L$ – left).
 - $N$ by $M$ matrix of digits between $0$ and $9$, inclusive; the digit in row $x$ and column $y$ represents the number in cell $(x, y)$ dedicated to bacterium $i$.

-----Output-----
The first and only line of output must contain the total duration of Luka’s game, in seconds. If the game will never end, output -1.

-----Examples-----
Sample Input 1:
3 3 1
2 2
1 1 R
010
000
000
Sample Output 1:
2

Sample Input 2:
3 4 2
2 2
3 4 R
2327
6009
2112
3 2 R
1310
2101
1301
Sample Output 2:
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in mandarin chinese, russian and vietnamese as well. 

There are two players A, B playing a game. Player A has a string s with him, and player B has string t with him. Both s and t consist only of lower case English letters and are of equal length. A makes the first move, then B, then A, and so on alternatively. Before the start of the game, the players know the content of both the strings s and t.

These players are building one other string w during the game. Initially, the string w is empty. In each move, a player removes any one character from their respective string and adds this character anywhere (at any position) in the string w (Note that w is a string at all times, and you can insert between characters or at the ends. It is not an empty array where you can add a character at any index. Please see the Explanations for further clarification). If at any stage of the game, the string w is of length greater than 1 and is a palindrome, then the player who made the last move wins. 

If even after the game finishes (ie. when both s and t have become empty strings), no one is able to make the string w a palindrome, then player B wins.

Given the strings s, and t, find out which of A, B will win the game, if both play optimally.

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

The first line of the input contains an integer T, corresponding to the number of test cases. The description of each testcase follows.
The first line of each testcase will contain the string s.
The second line of each testcase will contain the string t.

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

For each test case, output "A" or "B" (without quotes) corresponding to the situation, in a new line.

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

$Subtask 1 (20 points) : 1 ≤ T ≤ 500, All characters of string s are equal, All characters of string t are equal. 1 ≤ |s| = |t| ≤ 500$
$Subtask 2 (80 points) : 1 ≤ T ≤ 500, 1 ≤ |s| = |t| ≤ 500 $

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

ab

ab

aba

cde

ab

cd
----- Sample Output 1 ------ 
B

A

B
----- explanation 1 ------ 
Testcase 1: If A adds 'a' to w in the first move, B can add 'a' and make the string w = "aa", which is a palindrome, and hence win. Similarly, you can show that no matter what A plays, B can win. Hence the answer is B.

Testcase 2: Player A moves with 'a', player B can put any of the character 'c', 'd' or 'e', Now Player A can create a palindrome by adding 'a'.

Testcase 3: None of the players will be able to make a palindrome of length > 1. So B will win.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The teacher gave Anton a large geometry homework, but he didn't do it (as usual) as he participated in a regular round on Codeforces. In the task he was given a set of *n* lines defined by the equations *y*<==<=*k**i*·*x*<=+<=*b**i*. It was necessary to determine whether there is at least one point of intersection of two of these lines, that lays strictly inside the strip between *x*1<=&lt;<=*x*2. In other words, is it true that there are 1<=≤<=*i*<=&lt;<=*j*<=≤<=*n* and *x*',<=*y*', such that: 
 -  *y*'<==<=*k**i*<=*<=*x*'<=+<=*b**i*, that is, point (*x*',<=*y*') belongs to the line number *i*; -  *y*'<==<=*k**j*<=*<=*x*'<=+<=*b**j*, that is, point (*x*',<=*y*') belongs to the line number *j*; -  *x*1<=&lt;<=*x*'<=&lt;<=*x*2, that is, point (*x*',<=*y*') lies inside the strip bounded by *x*1<=&lt;<=*x*2. 
You can't leave Anton in trouble, can you? Write a program that solves the given task.

Input Specification:
The first line of the input contains an integer *n* (2<=≤<=*n*<=≤<=100<=000) — the number of lines in the task given to Anton. The second line contains integers *x*1 and *x*2 (<=-<=1<=000<=000<=≤<=*x*1<=&lt;<=*x*2<=≤<=1<=000<=000) defining the strip inside which you need to find a point of intersection of at least two lines.

The following *n* lines contain integers *k**i*, *b**i* (<=-<=1<=000<=000<=≤<=*k**i*,<=*b**i*<=≤<=1<=000<=000) — the descriptions of the lines. It is guaranteed that all lines are pairwise distinct, that is, for any two *i*<=≠<=*j* it is true that either *k**i*<=≠<=*k**j*, or *b**i*<=≠<=*b**j*.

Output Specification:
Print "Yes" (without quotes), if there is at least one intersection of two distinct lines, located strictly inside the strip. Otherwise print "No" (without quotes).

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

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

Note:
In the first sample there are intersections located on the border of the strip, but there are no intersections located strictly inside it.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
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: 

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 Specification:
The first line contains integer *m* (1<=≤<=*m*<=≤<=105) — 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 Specification:
In the first line print the number of cards you can put on the table. In the second line print the resulting stairs.

Demo Input:
['5\n1 2 3 4 5\n', '6\n1 1 2 2 3 3\n']

Demo Output:
['5\n5 4 3 2 1\n', '5\n1 2 3 2 1\n']

Note:
none

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