vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
=====Function Descriptions=====
Basic mathematical functions operate element-wise on arrays. They are available both as operator overloads and as functions in the NumPy module.

import numpy

a = numpy.array([1,2,3,4], float)
b = numpy.array([5,6,7,8], float)

print a + b                     #[  6.   8.  10.  12.]
print numpy.add(a, b)           #[  6.   8.  10.  12.]

print a - b                     #[-4. -4. -4. -4.]
print numpy.subtract(a, b)      #[-4. -4. -4. -4.]

print a * b                     #[  5.  12.  21.  32.]
print numpy.multiply(a, b)      #[  5.  12.  21.  32.]

print a / b                     #[ 0.2         0.33333333  0.42857143  0.5       ]
print numpy.divide(a, b)        #[ 0.2         0.33333333  0.42857143  0.5       ]

print a % b                     #[ 1.  2.  3.  4.]
print numpy.mod(a, b)           #[ 1.  2.  3.  4.]

print a**b                      #[  1.00000000e+00   6.40000000e+01   2.18700000e+03   6.55360000e+04]
print numpy.power(a, b)         #[  1.00000000e+00   6.40000000e+01   2.18700000e+03   6.55360000e+04]

=====Problem Statement=====
You are given two integer arrays, A and B of dimensions NXM.
Your task is to perform the following operations:
1. Add (A + B)
2. Subtract (A - B)
3. Multiply (A * B)
4. Integer Division (A / B)
5. Mod (A % B)
6. Power (A ** B)

=====Input Format=====
The first line contains two space separated integers, N and M.
The next N lines contains M space separated integers of array A.
The following N lines contains M space separated integers of array B.

=====Output Format=====
Print the result of each operation in the given order under Task.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Last weekend you and your friends went to visit the local farmer’s market at the town square. As you were standing around in a circle talking, you couldn’t help overhearing two of your friends musing over what sounded like an interesting problem: They were considering the number of ways in which you could all shake hands, such that everyone in the circle simultaneously shaked hands with one other person, but where no arms crossed each other.

After a few seconds’ thought you decided to join your two friends, to share (with them) the solution to their problem. “If we are $2n$ persons”, you said, “pick any particular person, and let that person shake hands with somebody. That person will have to leave an even number of people on each side of the person with whom he/she shakes hands. Of the remaining $n-1$ pairs of people, he/she can leave zero on the right and $n-1$ pairs on the left, $1$ on the right and $n-2$ pairs on the left, and so on. The pairs remaining on the right and left can independently choose any of the possible non-crossing handshake patterns, so the count $C_ n$ for $n$ pairs of people is given by:\[ C_ n = C_{n-1}C_0 + C_{n-2}C_1 + \ldots + C_1C_{n-2} + C_0C_{n-1}, \]

which, together with the fact that $C_0=C_1=1$, is just the definition of the Catalan numbers.” By consulting your handy combinatorics book, you find out that there is a much more efficient formula for calculating $C_ n$, namely:\[ C_ n = \frac{\binom {2n}{n}}{n+1}. \]

After a collective groan from the group, your particularly cheeky friend Val called out “Well, since we are at the town square, why don’t you try to square your Catalan numbers!”. This was met with much rejoicing, while you started to think about how to square the Catalan sequence…

-----Task-----
Let $C_ n$ be the $n$th Catalan number as defined above. By regarding the sequence $(C_ n)_{n\geq 0}$ of Catalan numbers, we can define a sequence $(S_ n)_{n\geq 0}$, corresponding to “squaring the Catalan sequence”, by considering the Cauchy product, or discrete convolution, of $(C_ n)_{n\geq 0}$ with itself, i.e.,\[ S_ n = \sum _{k=0}^{n}C_ kC_{n-k}. \]

Your task is to write a program for calculating the number $S_ n$.1

-----Input-----
The input contains one line containing one non-negative integer: $n$, with $0 \leq n \leq 5000$.

-----Output-----
Output a line containing $S_ n$.

-----Examples-----
Sample Input:
0
Sample Output:
1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus adores TV series. Right now he is ready to finish watching a season of a popular sitcom "Graph Theory". In total, the season has *n* episodes, numbered with integers from 1 to *n*.

Polycarpus watches episodes not one by one but in a random order. He has already watched all the episodes except for one. Which episode has Polycaprus forgotten to watch?

Input Specification:
The first line of the input contains integer *n* (2<=≤<=*n*<=≤<=100000) — the number of episodes in a season. Assume that the episodes are numbered by integers from 1 to *n*.

The second line contains *n*<=-<=1 integer *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=*n*) — the numbers of episodes that Polycarpus has watched. All values of *a**i* are distinct.

Output Specification:
Print the number of the episode that Polycarpus hasn't watched.

Demo Input:
['10\n3 8 10 1 7 9 6 5 2\n']

Demo Output:
['4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two linked lists sorted in increasing order, create a new linked list representing the intersection of the two linked lists. The new linked list should be made with its own memory the original lists should not be changed.
Note: The linked list elements are not necessarily distinct.
Example 1:
Input:
L1 = 1->2->3->4->6
L2 = 2->4->6->8
Output: 2 4 6
Explanation: For the given first two
linked list, 2, 4 and 6 are the elements
in the intersection.
Example 2:
Input:
L1 = 10->20->40->50
L2 = 15->40
Output: 40
Your Task:
The task is to complete the function intersection() which should find the intersection of two linked list and add all the elements in intersection to the third linked list and return the head of the third linked list.
Expected Time Complexity : O(n+m)
Expected Auxilliary Space : O(n+m)
Note: n,m are the size of the linked lists.
Constraints:
1 <= size of linked lists <= 5000
1 <= Data in linked list nodes <= 10^{4}

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
There is a string *s*, consisting of capital Latin letters. Let's denote its current length as |*s*|. During one move it is allowed to apply one of the following operations to it: 
 -  INSERT *pos* *ch* — insert a letter *ch* in the string *s* in the position *pos* (1<=≤<=*pos*<=≤<=|*s*|<=+<=1,<=*A*<=≤<=*ch*<=≤<=*Z*). The letter *ch* becomes the *pos*-th symbol of the string *s*, at that the letters shift aside and the length of the string increases by 1. -  DELETE *pos* — delete a character number *pos* (1<=≤<=*pos*<=≤<=|*s*|) from the string *s*. At that the letters shift together and the length of the string decreases by 1. -  REPLACE *pos* *ch* — the letter in the position *pos* of the line *s* is replaced by *ch* (1<=≤<=*pos*<=≤<=|*s*|,<=*A*<=≤<=*ch*<=≤<=*Z*). At that the length of the string does not change. 
Your task is to find in which minimal number of moves one can get a *t* string from an *s* string. You should also find the sequence of actions leading to the required results.

Input Specification:
The first line contains *s*, the second line contains *t*. The lines consist only of capital Latin letters, their lengths are positive numbers from 1 to 1000.

Output Specification:
In the first line print the number of moves *k* in the given sequence of operations. The number should be the minimal possible one. Then print *k* lines containing one operation each. Print the operations in the format, described above. If there are several solutions, print any of them.

Demo Input:
['ABA\nABBBA\n', 'ACCEPTED\nWRONGANSWER\n']

Demo Output:
['2\nINSERT 3 B\nINSERT 4 B\n', '10\nREPLACE 1 W\nREPLACE 2 R\nREPLACE 3 O\nREPLACE 4 N\nREPLACE 5 G\nREPLACE 6 A\nINSERT 7 N\nINSERT 8 S\nINSERT 9 W\nREPLACE 11 R\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're fed up about changing the version of your software manually. Instead, you will create a little script that will make it for you.

# Exercice

Create a function `nextVersion`, that will take a string in parameter, and will return a string containing the next version number.

For example:

# Rules

All numbers, except the first one, must be lower than 10: if there are, you have to set them to 0 and increment the next number in sequence.

You can assume all tests inputs to be valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are in charge of the cake for a child's birthday.  You have decided the cake will have one candle for each year of their total age. They will only be able to blow out the tallest of the candles. Count how many candles are tallest. 

Example  

$candles=[4,4,1,3]$

The maximum height candles are $4$ units high.  There are $2$ of them, so return $2$.

Function Description

Complete the function birthdayCakeCandles in the editor below.  

birthdayCakeCandles has the following parameter(s):

int candles[n]: the candle heights     

Returns  

int: the number of candles that are tallest

Input Format

The first line contains a single integer, $n$, the size of $\textit{candles[]}$. 

The second line contains $n$ space-separated integers, where each integer $\boldsymbol{i}$ describes the height of $\textit{candles}[i]$.

Constraints

$1\leq n\leq10^5$  
$1\leq\textit{candles}[i]\leq10^7$  

Sample Input 0
4
3 2 1 3

Sample Output 0
2

Explanation 0

Candle heights are $[3,2,1,3]$.  The tallest candles are $3$ units, and there are $2$ of them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.

There is a sequence a that consists of n integers a_1, a_2, ..., a_{n}. Let's denote f(l, r, x) the number of indices k such that: l ≤ k ≤ r and a_{k} = x. His task is to calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that f(1, i, a_{i}) > f(j, n, a_{j}).

Help Pashmak with the test.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 10^6). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a single integer — the answer to the problem.


-----Examples-----
Input
7
1 2 1 1 2 2 1

Output
8

Input
3
1 1 1

Output
1

Input
5
1 2 3 4 5

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The evil emperor Cactus has in his possession the Magic Keg and has flooded the Enchanted Forest! The Painter and the three little hedgehogs now have to return to the Beaver’s den where they will be safe from the water as quickly as possible!

The map of the Enchanted Forest consists of R rows and C columns. Empty fields are represented by ‘.’ characters, flooded fields by ‘*’ and rocks by ‘X’. Additionally, the Beaver’s den is represented by ‘D’ and the Painter and the three little hedgehogs are shown as ‘S’.

Every minute the Painter and the three little hedgehogs can move to one of the four neighbouring fields (up, down, left or right). Every minute the flood expands as well so that all empty fields that have at least one common side with a flooded field become flooded as well. Neither water nor the Painter and the three little hedgehogs can pass through rocks. Naturally, the Painter and the three little hedgehogs cannot pass through flooded fields, and water cannot flood the Beaver’s den.

Write a program that will, given a map of the Enchanted Forest, output the shortest time needed for the Painter and the three little hedgehogs to safely reach the Beaver’s den.

Note: The Painter and the three little hedgehogs cannot move into a field that is about to be flooded (in the same minute).

-----Input-----
The first line of input will contain two positive integers, $R$ and $C$, smaller than or equal to $50$. The following $R$ lines will each contain $C$ characters (‘.’, ‘*’, ‘X’, ‘D’ or ‘S’). The map will contain exactly one ‘D’ character and exactly one ‘S’ character.

-----Output-----
Output the shortest possible time needed for the Painter and the three little hedgehogs to safely reach the Beaver’s den. If this is impossible output the word “KAKTUS” on a line by itself.

Clarification of the second sample test below: The best they can do is to go along the lower border and then the left border, and get flooded one minute before reaching the den.

-----Examples-----
Sample Input 1:
3 3
D.*
...
.S.
Sample Output 1:
3

Sample Input 2:
3 3
D.*
...
..S
Sample Output 2:
KAKTUS

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The "Bulls and Cows" game needs two people to play. The thinker thinks of a number and the guesser tries to guess it.

The thinker thinks of a four-digit number in the decimal system. All the digits in the number are different and the number may have a leading zero. It can't have more than one leading zero, because all it's digits should be different. The guesser tries to guess the number. He makes a series of guesses, trying experimental numbers and receives answers from the first person in the format "*x* bulls *y* cows". *x* represents the number of digits in the experimental number that occupy the same positions as in the sought number. *y* represents the number of digits of the experimental number that present in the sought number, but occupy different positions. Naturally, the experimental numbers, as well as the sought number, are represented by four-digit numbers where all digits are different and a leading zero can be present.

For example, let's suppose that the thinker thought of the number 0123. Then the guessers' experimental number 1263 will receive a reply "1 bull 2 cows" (3 occupies the same positions in both numbers and 1 and 2 are present in both numbers but they occupy different positions). Also, the answer to number 8103 will be "2 bulls 1 cow" (analogically, 1 and 3 occupy the same positions and 0 occupies a different one). 

When the guesser is answered "4 bulls 0 cows", the game is over.

Now the guesser has already made several guesses and wants to know whether his next guess can possibly be the last one.

Input Specification:
The first input line contains an integer *n* (1<=≤<=*n*<=≤<=10) which represents the number of already made guesses. Then follow *n* lines in the form of "*a**i* *b**i* *c**i*", where *a**i* is the *i*-th experimental number, *b**i* is the number of bulls, *c**i* is the number of cows (1<=≤<=*i*<=≤<=*n*, 0<=≤<=*b**i*,<=*c**i*,<=*b**i*<=+<=*c**i*<=≤<=4). The experimental numbers are correct, i.e., each of them contains exactly four digits, in each of them all the four digits are different, and there can be a leading zero. All the experimental numbers are different. As the guesser hasn't guessed the number yet, the answer "4 bulls 0 cows" is not present.

Output Specification:
If the input data is enough to determine the sought number, print the number with four digits on a single line. If it has less than four digits, add leading zero. If the data is not enough, print "Need more data" without the quotes. If the thinker happens to have made a mistake in his replies, print "Incorrect data" without the quotes.

Demo Input:
['2\n1263 1 2\n8103 2 1\n', '2\n1234 2 2\n1256 0 2\n', '2\n0123 1 1\n4567 1 2\n']

Demo Output:
['Need more data', '2134', 'Incorrect data']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In AtCoder city, there are five antennas standing in a straight line. They are called Antenna A, B, C, D and E from west to east, and their coordinates are a, b, c, d and e, respectively.

Two antennas can communicate directly if the distance between them is k or less, and they cannot if the distance is greater than k.

Determine if there exists a pair of antennas that cannot communicate directly.

Here, assume that the distance between two antennas at coordinates p and q (p < q) is q - p.  

-----Constraints-----
 - a, b, c, d, e and k are integers between 0 and 123 (inclusive).
 - a < b < c < d < e

-----Input-----
Input is given from Standard Input in the following format:
a
b
c
d
e
k

-----Output-----
Print :( if there exists a pair of antennas that cannot communicate directly, and print Yay! if there is no such pair.

-----Sample Input-----
1
2
4
8
9
15

-----Sample Output-----
Yay!

In this case, there is no pair of antennas that cannot communicate directly, because:
 - the distance between A and B is 2 - 1 = 1
 - the distance between A and C is 4 - 1 = 3
 - the distance between A and D is 8 - 1 = 7
 - the distance between A and E is 9 - 1 = 8
 - the distance between B and C is 4 - 2 = 2
 - the distance between B and D is 8 - 2 = 6
 - the distance between B and E is 9 - 2 = 7
 - the distance between C and D is 8 - 4 = 4
 - the distance between C and E is 9 - 4 = 5
 - the distance between D and E is 9 - 8 = 1
and none of them is greater than 15. Thus, the correct output is Yay!.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the hard version of the problem. The only difference between easy and hard versions is the constraint of m. You can make hacks only if both versions are solved.

Chiori loves dolls and now she is going to decorate her bedroom!

<image>

As a doll collector, Chiori has got n dolls. The i-th doll has a non-negative integer value a_i (a_i < 2^m, m is given). Chiori wants to pick some (maybe zero) dolls for the decoration, so there are 2^n different picking ways.

Let x be the bitwise-xor-sum of values of dolls Chiori picks (in case Chiori picks no dolls x = 0). The value of this picking way is equal to the number of 1-bits in the binary representation of x. More formally, it is also equal to the number of indices 0 ≤ i < m, such that \left⌊ (x)/(2^i) \right⌋ is odd.

Tell her the number of picking ways with value i for each integer i from 0 to m. Due to the answers can be very huge, print them by modulo 998 244 353.

Input

The first line contains two integers n and m (1 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ m ≤ 53) — the number of dolls and the maximum value of the picking way.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i < 2^m) — the values of dolls.

Output

Print m+1 integers p_0, p_1, …, p_m — p_i is equal to the number of picking ways with value i by modulo 998 244 353.

Examples

Input


4 4
3 5 8 14


Output


2 2 6 6 0 

Input


6 7
11 45 14 9 19 81


Output


1 2 11 20 15 10 5 0 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are in charge of a server that needs to run some submitted tasks on a first-come, first-served basis. Each day, you can dedicate the server to run these tasks for at most $T$ minutes. Given the time each task takes, you want to know how many of them will be finished today.

Consider the following example. Assume $T = 180$ and the tasks take $45, 30, 55, 20, 80,$ and $20$ minutes (in order they are submitted). Then, only four tasks can be completed. The first four tasks can be completed because they take $150$ minutes, but not the first five, because they take $230$ minutes which is greater than $180$. Notice that although there is enough time to perform the sixth task (which takes $20$ minutes) after completing the fourth task, you cannot do that because the fifth task is not done yet.

-----Input-----
The input consists of a single test case. The first line contains two integers $n$ and $T$ where $1 \le n \le 50$ is the number of tasks and $1 \le T \le 500$. The next line contains $n$ positive integers no more than $100$ indicating how long each task takes in order they are submitted.

-----Output-----
Display the number of tasks that can be completed in $T$ minutes on a first-come, first-served basis.

-----Examples-----
Sample Input:
6 180
45 30 55 20 80 20
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a positive integer X, let f(X) be the number of positive divisors of X.
Given a positive integer N, find \sum_{K=1}^N K\times f(K).

-----Constraints-----
 - 1 \leq N \leq 10^7

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

-----Output-----
Print the value \sum_{K=1}^N K\times f(K).

-----Sample Input-----
4

-----Sample Output-----
23

We have f(1)=1, f(2)=2, f(3)=2, and f(4)=3, so the answer is 1\times 1 + 2\times 2 + 3\times 2 + 4\times 3 =23.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Buffalo Bill wishes to cross a $1000 \times 1000$ square field. A number of snakes are on the field at various positions, and each snake can strike a particular distance in any direction. Can Bill make the trip without being bitten?

Assume that the southwest corner of the field is at $(0,0)$ and the northwest corner at $(0,1000)$. Bill must enter the field somewhere between the southwest and northwest corner and must leave somewhere between the southeast and northeast corners.

-----Input-----
The input consists of a line containing $0 \le n \le 1000$, the number of snakes. A line follows for each snake, containing three integers: the $(x,y)$ location of the snake ($0 \le x, y \le 1000$) and its strike distance $1 \le d \le 1000$. The snake will bite anything that passes strictly closer than this distance from its location.

-----Output-----
If Bill can complete the trip, give coordinates with exactly two decimal digits at which he may enter and leave the field. Use the format shown in the sample input. If Bill may enter and leave at several places, give the most northerly. If there is no such pair of positions, print “Bill will be bitten.”

-----Examples-----
Sample Input 1:
3
500 500 499
0 0 999
1000 1000 200
Sample Output 1:
Bill enters at (0.00, 1000.00) and leaves at (1000.00, 800.00).

Sample Input 2:
4
250 250 300
750 250 300
250 750 300
750 750 300
Sample Output 2:
Bill will be bitten.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kyoya Ootori is selling photobooks of the Ouran High School Host Club. He has 26 photos, labeled "a" to "z", and he has compiled them into a photo booklet with some photos in some order (possibly with some photos being duplicated). A photo booklet can be described as a string of lowercase letters, consisting of the photos in the booklet in order. He now wants to sell some "special edition" photobooks, each with one extra photo inserted anywhere in the book. He wants to make as many distinct photobooks as possible, so he can make more money. He asks Haruhi, how many distinct photobooks can he make by inserting one extra photo into the photobook he already has?

Please help Haruhi solve this problem.

Input Specification:
The first line of input will be a single string *s* (1<=≤<=|*s*|<=≤<=20). String *s* consists only of lowercase English letters.

Output Specification:
Output a single integer equal to the number of distinct photobooks Kyoya Ootori can make.

Demo Input:
['a\n', 'hi\n']

Demo Output:
['51\n', '76\n']

Note:
In the first case, we can make 'ab','ac',...,'az','ba','ca',...,'za', and 'aa', producing a total of 51 distinct photo booklets.

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