vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. (Takoyaki is the name of a Japanese snack.)
To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.
What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?
Assume that you have sufficient numbers of banknotes, and so does the clerk.

-----Constraints-----
 - N is an integer between 1 and 10^{1,000,000} (inclusive).

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

-----Output-----
Print the minimum possible number of total banknotes used by you and the clerk.

-----Sample Input-----
36

-----Sample Output-----
8

If you give four banknotes of value 10 each, and the clerk gives you back four banknotes of value 1 each, a total of eight banknotes are used.
The payment cannot be made with less than eight banknotes in total, so the answer is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an Array and an Example-Array to sort to, write a function that sorts the Array following the Example-Array.

Assume Example Array catalogs all elements possibly seen in the input Array. However, the input Array does not necessarily have to have all elements seen in the Example.

Example:

Arr:
[1,3,4,4,4,4,5]

Example Arr:
[4,1,2,3,5]

Result:
[4,4,4,4,1,3,5]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers, $N$ and $\mbox{M}$. Count the number of strings of length $N$ (under the alphabet set of size $\mbox{M}$) that doesn't contain any palindromic string of the length greater than $\mbox{1}$ as a consecutive substring.

Input Format

Several test cases will be given to you in a single file. The first line of the input will contain a single integer, ${T}$, the number of test cases.

Then there will be ${T}$ lines, each containing two space-separated integers, $N$ and $\mbox{M}$, denoting a single test case. The meanings of $N$ and $\mbox{M}$ are described in the Problem Statement above.

Output Format

For each test case, output a single integer - the answer to the corresponding test case. This number can be huge, so output it modulo $10^9+7$.

Constraints  

$1\leq T\leq10^5$

$1\leq N,M\leq10^9$

Sample Input
2
2 2
2 3

Sample Output
2
6

Explanation

For the 1^{st} testcase, we have an alphabet of size M = 2. For the sake of simplicity, let's consider the alphabet as [A, B]. We can construct four strings of size N = 2 using these letters.

AA
AB
BA
BB

Out of these, we have two strings, AB and BA, that satisfy the condition of not having a palindromic string of length greater than 1. Hence, the answer 2.

For the 2^{nd} test case, we have an alphabet of size M = 3. For the sake of simplicity, let's consider the alphabet as [A, B, C]. We can construct nine strings of size N = 2 using these letters. 

AA
AB
AC
BA
BB
BC
CA
CB
CC

Save AA, BB, and CC, all the strings satisfy the given condition; hence, the answer 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Koa the Koala and her best friend want to play a game.

The game starts with an array $a$ of length $n$ consisting of non-negative integers. Koa and her best friend move in turns and each have initially a score equal to $0$. Koa starts.

Let's describe a move in the game:  During his move, a player chooses any element of the array and removes it from this array, xor-ing it with the current score of the player.

 More formally: if the current score of the player is $x$ and the chosen element is $y$, his new score will be $x \oplus y$. Here $\oplus$ denotes bitwise XOR operation.

 Note that after a move element $y$ is removed from $a$.

  The game ends when the array is empty. 

At the end of the game the winner is the player with the maximum score. If both players have the same score then it's a draw.

If both players play optimally find out whether Koa will win, lose or draw the game.


-----Input-----

Each test contains multiple test cases. The first line contains $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains the integer $n$ ($1 \le n \le 10^5$) — the length of $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — elements of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print:  WIN if Koa will win the game.  LOSE if Koa will lose the game.  DRAW if the game ends in a draw. 


-----Examples-----
Input
3
3
1 2 2
3
2 2 3
5
0 0 0 2 2

Output
WIN
LOSE
DRAW

Input
4
5
4 1 5 1 3
4
1 0 1 6
1
0
2
5 4

Output
WIN
WIN
DRAW
WIN



-----Note-----

In testcase $1$ of the first sample we have:

$a = [1, 2, 2]$. Here Koa chooses $1$, other player has to choose $2$, Koa chooses another $2$. Score for Koa is $1 \oplus 2 = 3$ and score for other player is $2$ so Koa wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the easy 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 ≤ 35) — 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.
Dark completed with studying Strings last night and trying to solve the problem of primes numbers from last three months but did not succeed every time he preferred to ask your help and same goes this time.

He likes to play a game with PRIMES AND STRINGS and he named the game as "PRIME ASCII CHARACTERS".

The rules are  as simple as finding the primes.

He wants you to read a string and delete all the characters whose ASCII VALUES is found to be a prime number.

Input:

The first line contains T, the number of test cases.
Followed by T lines each contains a single string 'S'.

Output:

For every test case print the string by removing the PRIME ASCII CHARACTERS.

print "NULL" If all the characters of a string are prime ascii characters.

Constraints:

1 ≤ T ≤ 10000
1 ≤ |S| ≤ 100000

Author : Darshak Mehta

Note: String contains only Alphabets both UPPER & LOWER CASES.

SAMPLE INPUT
4
MEHTA
Mehta
HELLO
hello

SAMPLE OUTPUT
MEHTA
Mht
HELL
hllo

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ujan has a lot of numbers in his boxes. He likes order and balance, so he decided to reorder the numbers.

There are $k$ boxes numbered from $1$ to $k$. The $i$-th box contains $n_i$ integer numbers. The integers can be negative. All of the integers are distinct. 

Ujan is lazy, so he will do the following reordering of the numbers exactly once. He will pick a single integer from each of the boxes, $k$ integers in total. Then he will insert the chosen numbers — one integer in each of the boxes, so that the number of integers in each box is the same as in the beginning. Note that he may also insert an integer he picked from a box back into the same box.

Ujan will be happy if the sum of the integers in each box is the same. Can he achieve this and make the boxes perfectly balanced, like all things should be?


-----Input-----

The first line contains a single integer $k$ ($1 \leq k \leq 15$), the number of boxes. 

The $i$-th of the next $k$ lines first contains a single integer $n_i$ ($1 \leq n_i \leq 5\,000$), the number of integers in box $i$. Then the same line contains $n_i$ integers $a_{i,1}, \ldots, a_{i,n_i}$ ($|a_{i,j}| \leq 10^9$), the integers in the $i$-th box. 

It is guaranteed that all $a_{i,j}$ are distinct.


-----Output-----

If Ujan cannot achieve his goal, output "No" in a single line. Otherwise in the first line output "Yes", and then output $k$ lines. The $i$-th of these lines should contain two integers $c_i$ and $p_i$. This means that Ujan should pick the integer $c_i$ from the $i$-th box and place it in the $p_i$-th box afterwards.

If there are multiple solutions, output any of those.

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


-----Examples-----
Input
4
3 1 7 4
2 3 2
2 8 5
1 10

Output
Yes
7 2
2 3
5 1
10 4

Input
2
2 3 -2
2 -1 5

Output
No

Input
2
2 -10 10
2 0 -20

Output
Yes
-10 2
-20 1



-----Note-----

In the first sample, Ujan can put the number $7$ in the $2$nd box, the number $2$ in the $3$rd box, the number $5$ in the $1$st box and keep the number $10$ in the same $4$th box. Then the boxes will contain numbers $\{1,5,4\}$, $\{3, 7\}$, $\{8,2\}$ and $\{10\}$. The sum in each box then is equal to $10$.

In the second sample, it is not possible to pick and redistribute the numbers in the required way.

In the third sample, one can swap the numbers $-20$ and $-10$, making the sum in each box equal to $-10$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is a system of *n* vessels arranged one above the other as shown in the figure below. Assume that the vessels are numbered from 1 to *n*, in the order from the highest to the lowest, the volume of the *i*-th vessel is *a**i* liters.

Initially, all the vessels are empty. In some vessels water is poured. All the water that overflows from the *i*-th vessel goes to the (*i*<=+<=1)-th one. The liquid that overflows from the *n*-th vessel spills on the floor.

Your task is to simulate pouring water into the vessels. To do this, you will need to handle two types of queries:
 1.  Add *x**i* liters of water to the *p**i*-th vessel; 1.  Print the number of liters of water in the *k**i*-th vessel. 
When you reply to the second request you can assume that all the water poured up to this point, has already overflown between the vessels.

Input Specification:
The first line contains integer *n* — the number of vessels (1<=≤<=*n*<=≤<=2·105). The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* — the vessels' capacities (1<=≤<=*a**i*<=≤<=109). The vessels' capacities do not necessarily increase from the top vessels to the bottom ones (see the second sample). The third line contains integer *m* — the number of queries (1<=≤<=*m*<=≤<=2·105). Each of the next *m* lines contains the description of one query. The query of the first type is represented as "1 *p**i* *x**i*", the query of the second type is represented as "2 *k**i*" (1<=≤<=*p**i*<=≤<=*n*, 1<=≤<=*x**i*<=≤<=109, 1<=≤<=*k**i*<=≤<=*n*).

Output Specification:
For each query, print on a single line the number of liters of water in the corresponding vessel.

Demo Input:
['2\n5 10\n6\n1 1 4\n2 1\n1 2 5\n1 1 4\n2 1\n2 2\n', '3\n5 10 8\n6\n1 1 12\n2 2\n1 1 6\n1 3 2\n2 2\n2 3\n']

Demo Output:
['4\n5\n8\n', '7\n10\n5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected graph of N nodes and M edges, E_1, E_2, ... E_M.

A connected graph is a cactus if each of it's edges belogs to at most one simple cycle. A graph is a desert if each of it's connected components is a cactus. 

Find the number of pairs (L, R), (1 ≤ L ≤ R ≤ M) such that, if we delete all the edges except for E_L, E_{L+1}, ... E_R, the graph is a desert. 

Input

The first line contains two integers N and M (2 ≤ N ≤ 2.5 × 10^5, 1 ≤ M ≤ 5 × 10^5). Each of the next M lines contains two integers. The i-th line describes the i-th edge. It contains integers U_i and V_i, the nodes connected by the i-th edge (E_i=(U_i, V_i)). It is guaranteed that 1 ≤ U_i, V_i ≤ N and U_i ≠ V_i. 

Output

The output contains one integer number – the answer.

Examples

Input


5 6
1 2
2 3
3 4
4 5
5 1
2 4


Output


20

Input


2 3
1 2
1 2
1 2


Output


5

Note

In the second example: Graphs for pairs (1, 1), (2, 2) and (3, 3) are deserts because they don't have any cycles. Graphs for pairs (1, 2) and (2, 3) have one cycle of length 2 so they are deserts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence $A_1, A_2, \ldots, A_N$. You want all the elements of the sequence to be equal. In order to achieve that, you may perform zero or more moves. In each move, you must choose an index $i$ ($1 \le i \le N$), then choose $j = i-1$ or $j = i+1$ (it is not allowed to choose $j = 0$ or $j = N+1$) and change the value of $A_i$ to $A_j$ — in other words, you should replace the value of one element of the sequence by one of its adjacent elements.
What is the minimum number of moves you need to make in order to make all the elements of the sequence equal?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the minimum required number of moves.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 100$
- $1 \le A_i \le 100$ for each valid $i$

-----Example Input-----
3
5
1 1 1 1 1
4
9 8 1 8
2
1 9

-----Example Output-----
0
2
1

-----Explanation-----
Example case 1: No moves are needed since all the elements are already equal.
Example case 3: We can perform one move on either $A_1$ or $A_2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have held a popularity poll for N items on sale. Item i received A_i votes.
From these N items, we will select M as popular items. However, we cannot select an item with less than \dfrac{1}{4M} of the total number of votes.
If M popular items can be selected, print Yes; otherwise, print No.

-----Constraints-----
 - 1 \leq M \leq N \leq 100
 - 1 \leq A_i \leq 1000
 - A_i are distinct.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 ... A_N

-----Output-----
If M popular items can be selected, print Yes; otherwise, print No.

-----Sample Input-----
4 1
5 4 2 1

-----Sample Output-----
Yes

There were 12 votes in total. The most popular item received 5 votes, and we can select it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S, in an operation you can remove 3 consecutive characters which are duplicates and concatenate the rest string. You can perform this operation any number of times. Find the reduced string.
Note: Return '-1' if the string is empty after removing the duplicates.
Example 1:
Input: S = "aabbbaccddddc"
Output: ccdc
Explanation: First remove 3 consecutive
b's and d's and then a's
Example 2:
Input: S = "aabbaccddc"
Output: aabbaccddc
Explanation: No three consecutive 
duplicates exists
Your Task:
You don't need to read input or print anything. Your task is to complete the function remove3ConsecutiveDuplicates() which takes a string S as input and returns the string. 
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
Constraints:
1 <= |S| <= 10^{5}
S contains lower case English alphabets

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Indraneel's student has given him data from two sets of experiments that the student has performed. Indraneel wants to establish a correlation between the two sets of data. Each data set is a sequence of $N$ numbers. The two data sets do not match number for number, but Indraneel believes that this is because data has been shifted due to inexact tuning of the equipment.
For example, consider the following two sequences:
$ $
3  8   4  23  9  11  28
2  3  22  26  8  16  12

$ $
Indraneel observes that if we consider the subsequences $3,4,23,9$ and $2,3,22,8$ and examine their successive differences we get $1,19,-14$. He considers these two subsequences to be "identical". He would like to find the longest such pair of subsequences so that the successive differences are identical. Your task is to help him do this.

-----Input:-----
The first line of the input will contain a single integer $N$ indicating the number of data points in each of Indraneel's student's data sets. This is followed by two lines, each containing $N$ integers.

-----Output:-----
The output consists of three lines. The first line of output contains a single integer indicating the length of the longest pair of subsequences (one from each sequence) that has identical successive differences. This is followed by two lines each containing the corresponding subsequences. If there is more than one answer, it suffices to print one.

-----Constraints:-----
- $1 \leq N \leq 150$.
- $0 \leq$ Each data point $\leq 1000$

-----Sample Input-----
7
3 8 4 23 9 11 28  
2 3 22 26 8 16 12 

-----Sample Output-----
4
3 4 23 9
2 3 22 8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive decimal number x.

Your task is to convert it to the "simple exponential notation".

Let x = a·10^{b}, where 1 ≤ a < 10, then in general case the "simple exponential notation" looks like "aEb". If b equals to zero, the part "Eb" should be skipped. If a is an integer, it should be written without decimal point. Also there should not be extra zeroes in a and b.


-----Input-----

The only line contains the positive decimal number x. The length of the line will not exceed 10^6. Note that you are given too large number, so you can't use standard built-in data types "float", "double" and other.


-----Output-----

Print the only line — the "simple exponential notation" of the given number x.


-----Examples-----
Input
16

Output
1.6E1

Input
01.23400

Output
1.234

Input
.100

Output
1E-1

Input
100.

Output
1E2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
N lamps are placed in a line, some are switched on and some are off. What is the smallest number of lamps that need to be switched so that on and off lamps will alternate with each other? 

You are given an array `a` of zeros and ones - `1` mean switched-on lamp and `0` means switched-off.

Your task is to find the smallest number of lamps that need to be switched.

# Example

For `a = [1, 0, 0, 1, 1, 1, 0]`, the result should be `3`.
```
a     --> 1 0 0 1 1 1 0
swith --> 0 1     0
became--> 0 1 0 1 0 1 0 ```

# Input/Output


- `[input]` integer array `a`

array of zeros and ones - initial lamp setup, 1 mean switched-on lamp and 0 means switched-off.

`2 < a.length <= 1000`


- `[output]` an integer

minimum number of switches.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, s, return a new string that orders the characters in order of frequency. 

The returned string should have the same number of characters as the original string. 

Make your transformation stable, meaning characters that compare equal should stay in their original order in the string s. 

```python
most_common("Hello world") => "lllooHe wrd"
most_common("Hello He worldwrd") => "lllHeo He wordwrd"
```

Explanation:

In the `hello world` example, there are 3 `'l'`characters, 2 `'o'`characters, and one each of `'H'`, `'e'`, `' '`, `'w'`, `'r'`, and `'d'`characters. Since `'He wrd'`are all tied, they occur in the same relative order that they do in the original string, `'Hello world'`.

Note that ties don't just happen in the case of characters occuring once in a string. See the second example, `most_common("Hello He worldwrd")`should return `'lllHeo He wordwrd'`, not `'lllHHeeoo  wwrrdd'`.  **This is a key behavior if this method were to be used to transform a string on multiple passes.**

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp plays a computer game (yet again). In this game, he fights monsters using magic spells.

There are two types of spells: fire spell of power $x$ deals $x$ damage to the monster, and lightning spell of power $y$ deals $y$ damage to the monster and doubles the damage of the next spell Polycarp casts. Each spell can be cast only once per battle, but Polycarp can cast them in any order.

For example, suppose that Polycarp knows three spells: a fire spell of power $5$, a lightning spell of power $1$, and a lightning spell of power $8$. There are $6$ ways to choose the order in which he casts the spells:

  first, second, third. This order deals $5 + 1 + 2 \cdot 8 = 22$ damage;  first, third, second. This order deals $5 + 8 + 2 \cdot 1 = 15$ damage;  second, first, third. This order deals $1 + 2 \cdot 5 + 8 = 19$ damage;  second, third, first. This order deals $1 + 2 \cdot 8 + 2 \cdot 5 = 27$ damage;  third, first, second. This order deals $8 + 2 \cdot 5 + 1 = 19$ damage;  third, second, first. This order deals $8 + 2 \cdot 1 + 2 \cdot 5 = 20$ damage. 

Initially, Polycarp knows $0$ spells. His spell set changes $n$ times, each time he either learns a new spell or forgets an already known one. After each change, calculate the maximum possible damage Polycarp may deal using the spells he knows.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of changes to the spell set.

Each of the next $n$ lines contains two integers $tp$ and $d$ ($0 \le tp_i \le 1$; $-10^9 \le d \le 10^9$; $d_i \neq 0$) — the description of the change. If $tp_i$ if equal to $0$, then Polycarp learns (or forgets) a fire spell, otherwise he learns (or forgets) a lightning spell.

If $d_i > 0$, then Polycarp learns a spell of power $d_i$. Otherwise, Polycarp forgets a spell with power $-d_i$, and it is guaranteed that he knew that spell before the change.

It is guaranteed that the powers of all spells Polycarp knows after each change are different (Polycarp never knows two spells with the same power).


-----Output-----

After each change, print the maximum damage Polycarp can deal with his current set of spells.


-----Example-----
Input
6
1 5
0 10
1 -5
0 5
1 11
0 -10

Output
5
25
10
15
36
21

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