vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The game of Memory is played with $N$ pairs of cards where each pair has the same picture, i.e. there are $N$ different pictures, and each of them appear on exactly two cards.

The cards are shuffled and placed face down on a large table. On each turn you flip two cards of your choice face up. If they match you remove them from the game, and if they don’t match, you turn them face down. The goal of the game is to remove all cards from the game.

Your strategy is simple:
 - If you know of two face-down cards which have the same picture, choose both of them.
 - Otherwise,
 - Turn a random card that you have not looked at before face up.
 - If it matches a card you have seen, turn the matching card face up (you have excellent memory).
 - If the first card did not match a card you had seen before, turn another random unknown card face up.

Given this strategy, what is the expected number of turns you have to play in order to finish the game?

-----Input-----
Input is a single integer $N$ indicating the number of pairs of cards.

-----Output-----
Output the expected number of turns needed to finish the game. This number must have an absolute or relative error of at most $10^{-6}$.

-----Limits-----
 - $1 \leq N \leq 1000$

-----Examples-----
Sample Input:
1
Sample Output:
1.000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to create a function called ```sum_arrays()``` in Python or ```addArrays``` in Javascript, which takes two arrays consisting of integers, and returns the sum of those two arrays.

The twist is that (for example) ```[3,2,9]``` does not equal ``` 3 + 2 + 9```, it would equal ```'3' + '2' + '9'``` converted to an integer for this kata, meaning it would equal ```329```. The output should be an array of the the sum  in a similar fashion to the input (for example, if the sum is ```341```, you would return ```[3,4,1]```). Examples are given below of what two arrays should return.
```python
[3,2,9],[1,2] --> [3,4,1]
[4,7,3],[1,2,3] --> [5,9,6]
[1],[5,7,6] --> [5,7,7]
```
If both arrays are empty, return an empty array.

In some cases, there will be an array containing a negative number as the first index in the array. In this case treat the whole number as a negative number. See below:
```python
[3,2,6,6],[-7,2,2,8] --> [-3,9,6,2] # 3266 + (-7228) = -3962
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Cheaterius's Problem

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Cheaterius is a famous in all the Berland astrologist, magician and wizard, and he also is a liar and a cheater. One of his latest inventions is Cheaterius' amulets! They bring luck and wealth, but are rather expensive. Cheaterius makes them himself. The technology of their making is kept secret. But we know that throughout long nights Cheaterius glues together domino pairs with super glue to get squares 2<=×<=2 which are the Cheaterius' magic amulets! 

After a hard night Cheaterius made *n* amulets. Everyone of them represents a square 2<=×<=2, every quarter contains 1 to 6 dots. Now he wants sort them into piles, every pile must contain similar amulets. Two amulets are called similar if they can be rotated by 90, 180 or 270 degrees so that the following condition is met: the numbers of dots in the corresponding quarters should be the same. It is forbidden to turn over the amulets.

Write a program that by the given amulets will find the number of piles on Cheaterius' desk.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=1000), where *n* is the number of amulets. Then the amulet's descriptions are contained. Every description occupies two lines and contains two numbers (from 1 to 6) in each line. Between every pair of amulets the line "**" is located.

Output Specification:
Print the required number of piles.

Demo Input:
['4\n31\n23\n**\n31\n23\n**\n13\n32\n**\n32\n13\n', '4\n51\n26\n**\n54\n35\n**\n25\n61\n**\n45\n53\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tanmay is a legendary spammer - everyone in the spamming world knows and admires his abilities to spam anyone, anytime, anywhere. He decided to guide one of his mentors, named Arjit, as part of the Apex body of spamming. 

Tanmay has no doubts on his skills of teaching and making his mentor, Arjit, learn about the art of spamming. But, he surely has serious doubt on Arjit's skills of learning, implementing and executing whatever he has decided to teach him as part of the syllabus of spamming.

Tanmay has sent Arjit to test his skills, but he's getting extremely anxious about the performance of his mentee. So, to calm himself down he asks you to help him find out the maximum and the minimum productivity attained by Arjit in his travel.

Arjit has the option to visit N Facebook groups - where every Facebook group has some potential which can be negative, zero or positive. Now, he can decide to visit a group if he wants to or not. (Depending on the lessons taught to him by the great master!) The total productivity attained by Arjit is the product of all the groups he decides to visit.

Given the values of all the groups, find out the maximum and minimum spamming potential he can achieve and let Tanmay know about it, so that he calm himself down.

Input format:
The first line contains an integer, T, denoting the number of test cases. Each line of the test case contains an integer, N, denoting the size of the array. The next line contains N integers, denoting the value of the numbers in the array.

Output format:
Print the maximum product you can obtain followed by the minimum product. A space separates both these outputs. Answer to each test case is on a new line.  

Constraints:
1 ≤ T ≤ 500
1 ≤ N ≤ 18
-10 ≤ Ni ≤ 10  

Note:
In some cases only one element may be considered for minimum or maximum product.
If the array is (1, 2, 3), minimum product is 1 whereas maximum product is 6.
When the array is (-1, -2), minimum product is -2 whereas maximum product is 2.

SAMPLE INPUT
2
4
1 0 2 10
3
0 0 0

SAMPLE OUTPUT
20 0
0 0

Explanation

In the first test case, the maximum product is the product of all the numbers except 0, whereas the minimum product is the product of all numbers including 0.
In the second test case, the maximum and minimum product both are 0 as 0 is the only available number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A rectangle can be split up into a grid of 1x1 squares, the amount of which being equal to the product of the two dimensions of the rectangle. Depending on the size of the rectangle, that grid of 1x1 squares can also be split up into larger squares, for example a 3x2 rectangle has a total of 8 squares, as there are 6 distinct 1x1 squares, and two possible 2x2 squares. A 4x3 rectangle contains 20 squares.
Your task is to write a function `findSquares` that returns the total number of squares for any given rectangle, the dimensions of which being given as two integers with the first always being equal to or greater than the second.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing the following game. There are n points on a plane. They are the vertices of a regular n-polygon. Points are labeled with integer numbers from 1 to n. Each pair of distinct points is connected by a diagonal, which is colored in one of 26 colors. Points are denoted by lowercase English letters. There are three stones positioned on three distinct vertices. All stones are the same. With one move you can move the stone to another free vertex along some diagonal. The color of this diagonal must be the same as the color of the diagonal, connecting another two stones. 

Your goal is to move stones in such way that the only vertices occupied by stones are 1, 2 and 3. You must achieve such position using minimal number of moves. Write a program which plays this game in an optimal way.

Input

In the first line there is one integer n (3 ≤ n ≤ 70) — the number of points. In the second line there are three space-separated integer from 1 to n — numbers of vertices, where stones are initially located.

Each of the following n lines contains n symbols — the matrix denoting the colors of the diagonals. Colors are denoted by lowercase English letters. The symbol j of line i denotes the color of diagonal between points i and j. Matrix is symmetric, so j-th symbol of i-th line is equal to i-th symbol of j-th line. Main diagonal is filled with '*' symbols because there is no diagonal, connecting point to itself.

Output

If there is no way to put stones on vertices 1, 2 and 3, print -1 on a single line. Otherwise, on the first line print minimal required number of moves and in the next lines print the description of each move, one move per line. To describe a move print two integers. The point from which to remove the stone, and the point to which move the stone. If there are several optimal solutions, print any of them.

Examples

Input

4
2 3 4
*aba
a*ab
ba*b
abb*


Output

1
4 1


Input

4
2 3 4
*abc
a*ab
ba*b
cbb*


Output

-1

Note

In the first example we can move stone from point 4 to point 1 because this points are connected by the diagonal of color 'a' and the diagonal connection point 2 and 3, where the other stones are located, are connected by the diagonal of the same color. After that stones will be on the points 1, 2 and 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Finish the solution so that it returns the sum of all the multiples of 3 or 5 **below** the number passed in. 

> Note: If the number is a multiple of **both** 3 and 5, only count it *once*.
> Also, if a number is negative, return 0(for languages that do have them)
  
###### *Courtesy of projecteuler.net*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bosky often helps his younger brother Nitin with his home work and also clears his doubts.

Today, Nitin learned about proper fractions. He went a step forward and tried to represent the same proper fraction in its decimal form, but runs into problems. He now seeks help from his brother Bosky.

Nitin is a very sincere learner, thus he wants his brother to help him but doesn't want him to completely solve the problem. He goes to his brother Bosky and asks him to help him wherever he gets stuck while representing the proper fraction in decimal expansion by telling the next digit in the decimal expansion.

Though Bosky is a bit busy today with his school project, he doesn't want to disappoint his brother. He is familiar with your brilliant programming skills and asks you to create a program to help his brother, which can output R th digit in the decimal expansion for a given proper fraction \frac{N}{D}.

Input:

Input will contain a number T denoting the number of test cases. 

Then T test cases follow, each one consisting 3 integers N D R
where N and D are numerator and denominator respectively.

Output

For each test case, output a single integer representing R th digit from the left in the decimal expansion. 

NOTE: The number is a proper fraction, hence the counting will always start after the decimal place. For eg. fraction \frac{1}{2} can be written as 0.5 so its first digit is 5 and all the digits after 5 are 0.

Constraints

1  ≤  T  ≤ 100

1  ≤ N ≤  D ≤ 1000000

1  ≤ R ≤ 1000000

SAMPLE INPUT
4
1 2 1
1 2 2
1 2 20
1234 12345 123

SAMPLE OUTPUT
5
0
0
7

Explanation

Case 1 : 1\; 2\; 1
\frac{1}{2} = 0.5 and 1st digit is 5.

Case 2 and 3: 
\frac{1}{2} = 0.50000000000000000000 
All digits after 5 are 0, hence the output is 0 and 0.

Case 4: Same logic!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Berland State University invites people from all over the world as guest students. You can come to the capital of Berland and study with the best teachers in the country.

Berland State University works every day of the week, but classes for guest students are held on the following schedule. You know the sequence of seven integers $a_1, a_2, \dots, a_7$ ($a_i = 0$ or $a_i = 1$):  $a_1=1$ if and only if there are classes for guest students on Sundays;  $a_2=1$ if and only if there are classes for guest students on Mondays;  ...   $a_7=1$ if and only if there are classes for guest students on Saturdays. 

The classes for guest students are held in at least one day of a week.

You want to visit the capital of Berland and spend the minimum number of days in it to study $k$ days as a guest student in Berland State University. Write a program to find the length of the shortest continuous period of days to stay in the capital to study exactly $k$ days as a guest student.


-----Input-----

The first line of the input contains integer $t$ ($1 \le t \le 10\,000$) — the number of test cases to process. For each test case independently solve the problem and print the answer. 

Each test case consists of two lines. The first of them contains integer $k$ ($1 \le k \le 10^8$) — the required number of days to study as a guest student. The second line contains exactly seven integers $a_1, a_2, \dots, a_7$ ($a_i = 0$ or $a_i = 1$) where $a_i=1$ if and only if classes for guest students are held on the $i$-th day of a week.


-----Output-----

Print $t$ lines, the $i$-th line should contain the answer for the $i$-th test case — the length of the shortest continuous period of days you need to stay to study exactly $k$ days as a guest student.


-----Example-----
Input
3
2
0 1 0 0 0 0 0
100000000
1 0 0 0 1 0 1
1
1 0 0 0 0 0 0

Output
8
233333332
1



-----Note-----

In the first test case you must arrive to the capital of Berland on Monday, have classes on this day, spend a week until next Monday and have classes on the next Monday. In total you need to spend $8$ days in the capital of Berland.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given an array and your task will be to determine if an array is in ascending or descending order and if it is rotated or not. 

Consider the array `[1,2,3,4,5,7,12]`. This array is sorted in `Ascending` order. If we rotate this array once to the left, we get `[12,1,2,3,4,5,7]` and twice-rotated we get `[7,12,1,2,3,4,5]`. These two rotated arrays are in `Rotated Ascending` order.

Similarly, the array `[9,6,5,3,1]` is in `Descending` order, but we can rotate it to get an array in `Rotated Descending` order: `[1,9,6,5,3]` or `[3,1,9,6,5]` etc.

Arrays will never be unsorted, except for those that are rotated as shown above. Arrays will always have an answer, as shown in the examples below.

More examples:
```Haskell
solve([1,2,3,4,5,7]) = "A" -- Ascending
solve([7,1,2,3,4,5]) = "RA" -- Rotated ascending
solve([4,5,6,1,2,3]) = "RA" -- Rotated ascending
solve([9,8,7,6]) = "D" -- Descending
solve([5,9,8,7,6]) = "RD" -- Rotated Descending
```
More examples in the test cases. 

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note: This kata is inspired by [Convert a Number to a String!](http://www.codewars.com/kata/convert-a-number-to-a-string/). Try that one too.

## Description

We need a function that can transform a string into a number. What ways of achieving this do you know?

Note: Don't worry, all inputs will be strings, and every string is a perfectly valid representation of an integral number.

## Examples

```python
stringToNumber("1234") == 1234
stringToNumber("605" ) == 605
stringToNumber("1405") == 1405
stringToNumber("-7"  ) == -7
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our child likes computer science very much, especially he likes binary trees.

Consider the sequence of n distinct positive integers: c1, c2, ..., cn. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex v, the weight of v is in the set {c1, c2, ..., cn}. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices' weights.

Given an integer m, can you for all s (1 ≤ s ≤ m) calculate the number of good vertex-weighted rooted binary trees with weight s? Please, check the samples for better understanding what trees are considered different.

We only want to know the answer modulo 998244353 (7 × 17 × 223 + 1, a prime number).

Input

The first line contains two integers n, m (1 ≤ n ≤ 105; 1 ≤ m ≤ 105). The second line contains n space-separated pairwise distinct integers c1, c2, ..., cn. (1 ≤ ci ≤ 105).

Output

Print m lines, each line containing a single integer. The i-th line must contain the number of good vertex-weighted rooted binary trees whose weight exactly equal to i. Print the answers modulo 998244353 (7 × 17 × 223 + 1, a prime number).

Examples

Input

2 3
1 2


Output

1
3
9


Input

3 10
9 4 3


Output

0
0
1
1
0
2
4
2
6
15


Input

5 10
13 10 6 4 15


Output

0
0
0
1
0
1
0
2
0
5

Note

In the first example, there are 9 good vertex-weighted rooted binary trees whose weight exactly equal to 3:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice has an $n\! \times \! m$ grid and a $2\! \times \! 2$ block. She would like to place her block in the grid. She must place it so that the block is axis-aligned and covers exactly $4$ grid cells.

Bob wants to prevent Alice from doing that. To do this, he places obstacles in some of the grid cells. After Bob places his obstacles, all $2\! \times \! 2$ subgrids of the grid should contain at least one obstacle. Bob wants to minimize the number of grid cells where he places obstacles.

Help Bob count the number of ways he can place the minimum number obstacles to prevent Alice from placing her block. Output this number modulo a prime number $p$. Note that the answer is not the minimum number of obstacles, but rather the count of the number of ways Bob can place the minimum number of obstacles. For example, if $n=m=2$ for a $2\! \times \! 2$ grid, Bob only has to place $1$ obstacle, but there are $4$ ways to place it, so the answer in this case is $4$.

-----Input-----
The single line of input contains three space-separated integers $n$ ($2 \leq n \leq 25$), $m$ ($2 \leq m \leq 10^3$) and $p$ ($10^8 \leq p \leq 10^9+7$, $p$ is a prime number), where Alice’s grid is of size $n\! \times \! m$, and $p$ is a large prime modulus.

-----Output-----
Output a single integer, which is the number of ways Bob can place the minimum number of obstacles in the $n\! \times \! m$ grid to prevent Alice from placing her $2 \! \times \! 2$ block. Since this may be very large, output it modulo $p$.

-----Examples-----
Sample Input:
4 4 999999937
Sample Output:
79

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a sequence of numbers *a*1,<=*a*2,<=...,<=*a**n*, and a number *m*.

Check if it is possible to choose a non-empty subsequence *a**i**j* such that the sum of numbers in this subsequence is divisible by *m*.

Input Specification:
The first line contains two numbers, *n* and *m* (1<=≤<=*n*<=≤<=106, 2<=≤<=*m*<=≤<=103) — the size of the original sequence and the number such that sum should be divisible by it.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=109).

Output Specification:
In the single line print either "YES" (without the quotes) if there exists the sought subsequence, or "NO" (without the quotes), if such subsequence doesn't exist.

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

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

Note:
In the first sample test you can choose numbers 2 and 3, the sum of which is divisible by 5.

In the second sample test the single non-empty subsequence of numbers is a single number 5. Number 5 is not divisible by 6, that is, the sought subsequence doesn't exist.

In the third sample test you need to choose two numbers 3 on the ends.

In the fourth sample test you can take the whole subsequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The snakes want to build a temple for Lord Cobra. There are multiple strips of land that they are looking at, but not all of them are suitable. They need the strip of land to resemble a coiled Cobra. You need to find out which strips do so.
Formally, every strip of land, has a length. Suppose the length of the i-th strip is is Ni, then there will be Ni integers, Hi1, Hi2, .. HiNi, which represent the heights of the ground at various parts of the strip, in sequential order. That is, the strip has been divided into Ni parts and the height of each part is given. This strip is valid, if and only if all these conditions are satisfied:
- There should be an unique 'centre' part. This is where the actual temple will be built. By centre, we mean that there should be an equal number of parts to the left of this part, and to the right of this part.
- Hi1 = 1
- The heights keep increasing by exactly 1, as you move from the leftmost part, to the centre part.
- The heights should keep decreasing by exactly 1, as you move from the centre part to the rightmost part. Note that this means that HiNi should also be 1.
Your job is to look at every strip and find if it's valid or not.

-----Input-----
- The first line contains a single integer, S, which is the number of strips you need to look at. The description of each of the S strips follows
- The first line of the i-th strip's description will contain a single integer: Ni, which is the length and number of parts into which it has been divided.
- The next line contains Ni integers: Hi1, Hi2, .., HiNi. These represent the heights of the various parts in the i-th strip.

-----Output-----
- For each strip, in a new line, output "yes" if is a valid strip, and "no", if it isn't.

-----Constraints-----
- 1 ≤ S ≤ 100 
- 3 ≤ Ni ≤ 100 
- 1 ≤ Hij ≤ 100 

-----Example-----
Input:
7
5
1 2 3 2 1
7
2 3 4 5 4 3 2
5
1 2 3 4 3
5
1 3 5 3 1
7
1 2 3 4 3 2 1
4
1 2 3 2
4
1 2 2 1

Output:
yes
no
no
no
yes
no
no

-----Explanation-----
In the first strip, all the conditions are satisfied, hence it is valid.
In the second strip, it does not start with a 1, and hence is invalid.
In the third strip, it keeps increasing even past the centre, instead of decreasing. Hence invalid.
The fourth strip does not increase and decrease by exactly 1. Hence invalid.
The fifth satisfies all conditions and hence is valid.
The sixth and seventh strip do not have a 'centre' part. Because for every part, there are either more parts to its right than its left, or more parts on its left than its right. Hence both the strips are invalid.

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