vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Spreadsheet

Time Limit: 10 seconds

Memory Limit: 64 megabytes

Problem Description:
In the popular spreadsheets systems (for example, in Excel) the following numeration of columns is used. The first column has number A, the second — number B, etc. till column 26 that is marked by Z. Then there are two-letter numbers: column 27 has number AA, 28 — AB, column 52 is marked by AZ. After ZZ there follow three-letter numbers, etc.

The rows are marked by integer numbers starting with 1. The cell name is the concatenation of the column and the row numbers. For example, BC23 is the name for the cell that is in column 55, row 23. 

Sometimes another numeration system is used: RXCY, where X and Y are integer numbers, showing the column and the row numbers respectfully. For instance, R23C55 is the cell from the previous example.

Your task is to write a program that reads the given sequence of cell coordinates and produce each item written according to the rules of another numeration system.

Input Specification:
The first line of the input contains integer number *n* (1<=≤<=*n*<=≤<=105), the number of coordinates in the test. Then there follow *n* lines, each of them contains coordinates. All the coordinates are correct, there are no cells with the column and/or the row numbers larger than 106 .

Output Specification:
Write *n* lines, each line should contain a cell coordinates in the other numeration system.

Demo Input:
['2\nR23C55\nBC23\n']

Demo Output:
['BC23\nR23C55\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a set of consecutive numbers from ```1``` to ```n```.
We want to count all the subsets that do not contain consecutive numbers.
E.g.

If our set ```S1``` is equal to ```[1,2,3,4,5]```
The subsets that fulfill these property are:
```
[1],[2],[3],[4],[5],[1,3],[1,4],[1,5],[2,4],[2,5],[3,5],[1,3,5]
```
A total of      ```12   ``` subsets.

From the set ```S2``` equals to```[1,2,3]```, it is obvious that we have only ```4``` subsets and are:
```
[1],[2],[3],[1,3]
```
Make a code that may give the amount of all these subsets for any integer       ```n >= 2       ```.

Features of the random tests:
```
number of tests = 100 
10 <= n <= 120
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n squirrel(s) waiting below the feet of m chestnut tree(s). The first chestnut of the i-th tree will fall right after T_{i} second(s), and one more every P_{i} second(s) after that. The “big mama” of squirrels wants them to bring their nest no less than k chestnuts to avoid the big storm coming, as fast as possible! So they are discussing to wait below which trees to take enough chestnuts in the shortest time. Time to move to the positions is zero, and the squirrels move nowhere after that.

------ Request ------ 

Calculate the shortest time (how many seconds more) the squirrels can take enough chestnuts.

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

The first line contains an integer t, the number of test cases, for each:
The first line contains the integers m,n,k, respectively.
The second line contains the integers T_{i}  (i=1..m), respectively.
The third line contains the integers P_{i}  (i=1..m), respectively.

(Each integer on a same line is separated by at least one space character, there is no added line between test cases)

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

For each test cases, output in a single line an integer which is the shortest time calculated.

------ Limitations ------ 

0
0
07
0i,P_{i}≤100

----- Sample Input 1 ------ 
2
3 2 5
5 1 2
1 2 1
3 2 5
5 1 2
1 1 1
----- Sample Output 1 ------ 
4
3
----- explanation 1 ------ 
Test case $1$: Two squirrels wait below trees $2$ and $3$.
- After $1$ second, a chestnut from tree $2$ falls. Total chestnuts the squirrels have is $1$.
- After $2$ seconds, a chestnut from tree $3$ falls. Total chestnuts the squirrels have is $2$.
- After $3$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $4$.
- After $4$ seconds, a chestnut from tree $3$ falls. Total chestnuts the squirrels have is $5$.

Total time to gather $5$ chestnuts is $5$ seconds.

Test case $2$: Two squirrels wait below trees $2$ and $3$.
- After $1$ second, a chestnut from tree $2$ falls. Total chestnuts the squirrels have is $1$.
- After $2$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $3$.
- After $3$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $5$.

Total time to gather $5$ chestnuts is $3$ seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
zscoder has a deck of n+m custom-made cards, which consists of n cards labelled from 1 to n and m jokers. Since zscoder is lonely, he wants to play a game with himself using those cards. 

Initially, the deck is shuffled uniformly randomly and placed on the table. zscoder has a set S which is initially empty. 

Every second, zscoder draws the top card from the deck. 

  * If the card has a number x written on it, zscoder removes the card and adds x to the set S. 
  * If the card drawn is a joker, zscoder places all the cards back into the deck and reshuffles (uniformly randomly) the n+m cards to form a new deck (hence the new deck now contains all cards from 1 to n and the m jokers). Then, if S currently contains all the elements from 1 to n, the game ends. Shuffling the deck doesn't take time at all. 



What is the expected number of seconds before the game ends? We can show that the answer can be written in the form P/Q where P, Q are relatively prime integers and Q ≠ 0 mod 998244353. Output the value of (P ⋅ Q^{-1}) modulo 998244353.

Input

The only line of the input contains two integers n and m (1 ≤ n, m ≤ 2 ⋅ 10^{6}).

Output

Output a single integer, the value of (P ⋅ Q^{-1}) modulo 998244353.

Examples

Input


2 1


Output


5


Input


3 2


Output


332748127


Input


14 9


Output


969862773

Note

For the first sample, it can be proven that the expected time before the game ends is 5 seconds.

For the second sample, it can be proven that the expected time before the game ends is 28/3 seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Many students live in a dormitory. A dormitory is a whole new world of funny amusements and possibilities but it does have its drawbacks. 

There is only one shower and there are multiple students who wish to have a shower in the morning. That's why every morning there is a line of five people in front of the dormitory shower door. As soon as the shower opens, the first person from the line enters the shower. After a while the first person leaves the shower and the next person enters the shower. The process continues until everybody in the line has a shower.

Having a shower takes some time, so the students in the line talk as they wait. At each moment of time the students talk in pairs: the (2i - 1)-th man in the line (for the current moment) talks with the (2i)-th one. 

Let's look at this process in more detail. Let's number the people from 1 to 5. Let's assume that the line initially looks as 23154 (person number 2 stands at the beginning of the line). Then, before the shower opens, 2 talks with 3, 1 talks with 5, 4 doesn't talk with anyone. Then 2 enters the shower. While 2 has a shower, 3 and 1 talk, 5 and 4 talk too. Then, 3 enters the shower. While 3 has a shower, 1 and 5 talk, 4 doesn't talk to anyone. Then 1 enters the shower and while he is there, 5 and 4 talk. Then 5 enters the shower, and then 4 enters the shower.

We know that if students i and j talk, then the i-th student's happiness increases by g_{ij} and the j-th student's happiness increases by g_{ji}. Your task is to find such initial order of students in the line that the total happiness of all students will be maximum in the end. Please note that some pair of students may have a talk several times. In the example above students 1 and 5 talk while they wait for the shower to open and while 3 has a shower.


-----Input-----

The input consists of five lines, each line contains five space-separated integers: the j-th number in the i-th line shows g_{ij} (0 ≤ g_{ij} ≤ 10^5). It is guaranteed that g_{ii} = 0 for all i.

Assume that the students are numbered from 1 to 5.


-----Output-----

Print a single integer — the maximum possible total happiness of the students.


-----Examples-----
Input
0 0 0 0 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 0 0 0

Output
32

Input
0 43 21 18 2
3 0 21 11 65
5 2 0 1 4
54 62 12 0 99
87 64 81 33 0

Output
620



-----Note-----

In the first sample, the optimal arrangement of the line is 23154. In this case, the total happiness equals:

(g_23 + g_32 + g_15 + g_51) + (g_13 + g_31 + g_54 + g_45) + (g_15 + g_51) + (g_54 + g_45) = 32.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko and Slavko’s favourite pastime is competing against each other in mathematical games. This time they took a heap of $N$ pebbles and settled on the following rules:
 - Mirko is the first to play, then Slavko, then Mirko again, then Slavko and so on;
 - Mirko can take any number of pebbles (between $1$ and $N$, inclusive) from the heap during his first move;
 - In each of the following turns the current player must take at least $1$ pebble and is allowed to take at most double the amount of pebbles taken during the previous turn by the other player; naturally, one cannot take more pebbles than the remaining amount in the heap;
 - The player who takes the last pebble is the winner.

Both Mirko and Slavko play optimally (if it is possible for one player to beat the other, that player will always win). We need to find the minimum number of pebbles that Mirko must take during his first turn such that he is guaranteed to win the game.

-----Input-----
The first and only line of input contains the positive integer $N$ ($2 \le N \le 10^{15}$), the number of pebbles in the starting heap.

-----Output-----
The first and only line of output must contain the required minimum number of pebbles that Mirko needs to remove during his first turn.

-----Explanation of Sample Input 1-----
Mirko has $4$ possibilities to choose from: he can take $1$, $2$, $3$, or $4$ pebbles from the heap. If he takes all $4$ pebbles he will naturally win, but that is not the minimum solution. We need to check the remaining alternatives. If Mirko takes only one pebble, Slavko is left with a heap of $3$, but he can take at most $2$. Slavko cannot take all pebbles, but Mirko will be able to take all remaining pebbles during his next turn, winning the game. We conclude that $1$ is the minimum solution for this test case.

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

Sample Input 2:
7
Sample Output 2:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a string S of length N consisting of A, B, and C.
You can do the following operation on S zero or more times:
 - Choose i (1 \leq i \leq |S| - 1) such that S_i \neq S_{i + 1}. Replace S_i with the character (among A, B, and C) that is different from both S_i and S_{i + 1}, and remove S_{i + 1} from S.
Find the number of distinct strings that S can be after zero or more operations, and print the count modulo (10^9+7).

-----Constraints-----
 - 1 \leq N \leq 10^6
 - S is a string of length N consisting of A, B, and C.

-----Input-----
Input is given from Standard Input in the following format:
N
S

-----Output-----
Print the number of distinct strings that S can be after zero or more operations, modulo (10^9+7).

-----Sample Input-----
5
ABAAC

-----Sample Output-----
11

For example, the following sequence of operations turns S into ACB:
 - First, choose i=2. We replace S_2 with C and remove S_3, turning S into ACAC.
 - Then, choose i=3. We replace S_3 with B and remove S_4, turning S into ACB.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to calculate sum  of primes present as digits of given number N.
Example 1:
Input: 333
Output: 9
Explaination: 3 is a prime number. It 
is present 3 times. So 3+3+3 = 9.
Example 2:
Input: 686
Output: 0
Explaination: Neither 6 nor 8 is a 
prime number.
Your Task:
You do not need to read input or print anything. Your task is to complete the function primeSum() which takes N as input parameter and returns the sum of all the prime digits present in the number N.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 5*10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to decode some pattern problems, Chef wants your help to code it. Chef has one number K(odd) 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
3
5
7

-----Sample Output:-----
1
111
111
111
11111
11 11
1 1 1
11 11
11111
1111111
11   11
1 1 1 1
1  1  1
1 1 1 1
11   11
1111111

-----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.
You are given $n$ integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the $n$ numbers may not be chosen.

A rectangle (rectangular matrix) is called beautiful if in each row and in each column all values are different.

What is the largest (by the total number of cells) beautiful rectangle you can construct? Print the rectangle itself.


-----Input-----

The first line contains $n$ ($1 \le n \le 4\cdot10^5$). The second line contains $n$ integers ($1 \le a_i \le 10^9$).


-----Output-----

In the first line print $x$ ($1 \le x \le n$) — the total number of cells of the required maximum beautiful rectangle. In the second line print $p$ and $q$ ($p \cdot q=x$): its sizes. In the next $p$ lines print the required rectangle itself. If there are several answers, print any.


-----Examples-----
Input
12
3 1 4 1 5 9 2 6 5 3 5 8

Output
12
3 4
1 2 3 5
3 1 5 4
5 6 8 9

Input
5
1 1 1 1 1

Output
1
1 1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There’s a new art installation in town, and it inspires you…to play a childish game. The art installation consists of a floor with an $n\! \times \! n$ matrix of square tiles. Each tile holds a single number from $1$ to $k$. You want to play hopscotch on it. You want to start on some tile numbered $1$, then hop to some tile numbered $2$, then $3$, and so on, until you reach some tile numbered $k$. You are a good hopper, so you can hop any required distance. You visit exactly one tile of each number from $1$ to $k$.

What’s the shortest possible total distance over a complete game of Hopscotch? Use the Manhattan distance: the distance between the tile at $(x_1,y_1)$ and the tile at $(x_2,y_2)$ is $|x_1-x_2| + |y_1-y_2|$.

-----Input-----
The first line of input contains two space-separated integers $n$ ($1 \le n \le 50$) and $k$ ($1 \le k \le n^2$), where the art installation consists of an $n\! \times \! n$ matrix with tiles having numbers from $1$ to $k$.

Each of the next $n$ lines contains $n$ space-separated integers $x$ ($1 \le x \le k$). This is the art installation.

-----Output-----
Output a single integer, which is the total length of the shortest path starting from some $1$ tile and ending at some $k$ tile, or $-1$ if it isn’t possible.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is the faculty of Computer Science in Berland. In the social net "TheContact!" for each course of this faculty there is the special group whose name equals the year of university entrance of corresponding course of students at the university. 

Each of students joins the group of his course and joins all groups for which the year of student's university entrance differs by no more than x from the year of university entrance of this student, where x — some non-negative integer. A value x is not given, but it can be uniquely determined from the available data. Note that students don't join other groups. 

You are given the list of groups which the student Igor joined. According to this information you need to determine the year of Igor's university entrance.


-----Input-----

The first line contains the positive odd integer n (1 ≤ n ≤ 5) — the number of groups which Igor joined. 

The next line contains n distinct integers a_1, a_2, ..., a_{n} (2010 ≤ a_{i} ≤ 2100) — years of student's university entrance for each group in which Igor is the member.

It is guaranteed that the input data is correct and the answer always exists. Groups are given randomly.


-----Output-----

Print the year of Igor's university entrance. 


-----Examples-----
Input
3
2014 2016 2015

Output
2015

Input
1
2050

Output
2050



-----Note-----

In the first test the value x = 1. Igor entered the university in 2015. So he joined groups members of which are students who entered the university in 2014, 2015 and 2016.

In the second test the value x = 0. Igor entered only the group which corresponds to the year of his university entrance.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The famous joke programming language HQ9+ has only 4 commands. In this problem we will explore its subset — a language called HQ...

Input Specification:
The only line of the input is a string between 1 and 106 characters long.

Output Specification:
Output "Yes" or "No".

Demo Input:
['HHHH\n', 'HQHQH\n', 'HHQHHQH\n', 'HHQQHHQQHH\n']

Demo Output:
['Yes\n', 'No\n', 'No\n', 'Yes\n']

Note:
The rest of the problem statement was destroyed by a stray raccoon. We are terribly sorry for the inconvenience.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has $n$ different binary words. A word called binary if it contains only characters '0' and '1'. For example, these words are binary: "0001", "11", "0" and "0011100".

Polycarp wants to offer his set of $n$ binary words to play a game "words". In this game, players name words and each next word (starting from the second) must start with the last character of the previous word. The first word can be any. For example, these sequence of words can be named during the game: "0101", "1", "10", "00", "00001".

Word reversal is the operation of reversing the order of the characters. For example, the word "0111" after the reversal becomes "1110", the word "11010" after the reversal becomes "01011".

Probably, Polycarp has such a set of words that there is no way to put them in the order correspondent to the game rules. In this situation, he wants to reverse some words from his set so that:  the final set of $n$ words still contains different words (i.e. all words are unique);  there is a way to put all words of the final set of words in the order so that the final sequence of $n$ words is consistent with the game rules. 

Polycarp wants to reverse minimal number of words. Please, help him.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

The first line of a test case contains one integer $n$ ($1 \le n \le 2\cdot10^5$) — the number of words in the Polycarp's set. Next $n$ lines contain these words. All of $n$ words aren't empty and contains only characters '0' and '1'. The sum of word lengths doesn't exceed $4\cdot10^6$. All words are different.

Guaranteed, that the sum of $n$ for all test cases in the input doesn't exceed $2\cdot10^5$. Also, guaranteed that the sum of word lengths for all test cases in the input doesn't exceed $4\cdot10^6$.


-----Output-----

Print answer for all of $t$ test cases in the order they appear.

If there is no answer for the test case, print -1. Otherwise, the first line of the output should contain $k$ ($0 \le k \le n$) — the minimal number of words in the set which should be reversed. The second line of the output should contain $k$ distinct integers — the indexes of the words in the set which should be reversed. Words are numerated from $1$ to $n$ in the order they appear. If $k=0$ you can skip this line (or you can print an empty line). If there are many answers you can print any of them.


-----Example-----
Input
4
4
0001
1000
0011
0111
3
010
101
0
2
00000
00001
4
01
001
0001
00001

Output
1
3 
-1
0

2
1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarpus loves hamburgers very much. He especially adores the hamburgers he makes with his own hands. Polycarpus thinks that there are only three decent ingredients to make hamburgers from: a bread, sausage and cheese. He writes down the recipe of his favorite "Le Hamburger de Polycarpus" as a string of letters 'B' (bread), 'S' (sausage) и 'C' (cheese). The ingredients in the recipe go from bottom to top, for example, recipe "ВSCBS" represents the hamburger where the ingredients go from bottom to top as bread, sausage, cheese, bread and sausage again.

Polycarpus has n_{b} pieces of bread, n_{s} pieces of sausage and n_{c} pieces of cheese in the kitchen. Besides, the shop nearby has all three ingredients, the prices are p_{b} rubles for a piece of bread, p_{s} for a piece of sausage and p_{c} for a piece of cheese.

Polycarpus has r rubles and he is ready to shop on them. What maximum number of hamburgers can he cook? You can assume that Polycarpus cannot break or slice any of the pieces of bread, sausage or cheese. Besides, the shop has an unlimited number of pieces of each ingredient.


-----Input-----

The first line of the input contains a non-empty string that describes the recipe of "Le Hamburger de Polycarpus". The length of the string doesn't exceed 100, the string contains only letters 'B' (uppercase English B), 'S' (uppercase English S) and 'C' (uppercase English C).

The second line contains three integers n_{b}, n_{s}, n_{c} (1 ≤ n_{b}, n_{s}, n_{c} ≤ 100) — the number of the pieces of bread, sausage and cheese on Polycarpus' kitchen. The third line contains three integers p_{b}, p_{s}, p_{c} (1 ≤ p_{b}, p_{s}, p_{c} ≤ 100) — the price of one piece of bread, sausage and cheese in the shop. Finally, the fourth line contains integer r (1 ≤ r ≤ 10^12) — the number of rubles Polycarpus has.

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


-----Output-----

Print the maximum number of hamburgers Polycarpus can make. If he can't make any hamburger, print 0.


-----Examples-----
Input
BBBSSC
6 4 1
1 2 3
4

Output
2

Input
BBC
1 10 1
1 10 1
21

Output
7

Input
BSC
1 1 1
1 1 3
1000000000000

Output
200000000001

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