vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ehab has an array $a$ of length $n$. He has just enough free time to make a new array consisting of $n$ copies of the old array, written back-to-back. What will be the length of the new array's longest increasing subsequence?

A sequence $a$ is a subsequence of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements. The longest increasing subsequence of an array is the longest subsequence such that its elements are ordered in strictly increasing order.


-----Input-----

The first line contains an integer $t$ — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$) — the number of elements in the array $a$.

The second line contains $n$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_{n}$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.

The sum of $n$ across the test cases doesn't exceed $10^5$.


-----Output-----

For each testcase, output the length of the longest increasing subsequence of $a$ if you concatenate it to itself $n$ times.


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

Output
3
5



-----Note-----

In the first sample, the new array is $[3,2,\textbf{1},3,\textbf{2},1,\textbf{3},2,1]$. The longest increasing subsequence is marked in bold.

In the second sample, the longest increasing subsequence will be $[1,3,4,5,9]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day you were visiting a museum where you saw a modern piece of art that shows a grid of $N$ rows and $M$ columns. Each cell in the grid has a color, which can be one of the four: red (‘R’), green (‘G’), blue (‘B’), and white (‘W’).

You think that the art is so simple so that even you can reproduce it yourself. After getting home, you get yourself a grid board with exactly $N$ rows and $M$ columns. The cells of the board are initially all white. You also find some red, green and blue paint (unfortunately you didn’t find any white paint), as well as a square stamp of a size equal to exactly $3 \times 3$ cells. With the tools at hand, in each step you can choose a square of $3\times 3$ cells from the board and pick a color, and then stamp the chosen square of cells with that color (overwriting their previous colors). Note that the chosen square is not allowed to exceed the board boundary, otherwise you would spill the paint and make your home messy.

You soon realize that the art seems to be simple but is not so easy to reproduce. Actually, you are not even sure about whether it is possible to reproduce the art with the aforementioned procedure. You eventually decide to make it a ProgNova question and ask some smart people for help.

-----Input-----
The first line contains two integers $N$ and $M$ ($3 \leq N, M \leq 30$). Each of the next $N$ lines has a string of $M$ characters. All strings contain only letters ‘R’, ‘G’, ‘B’, and ‘W’, representing the colors of the cells in the art piece you want to reproduce.

-----Output-----
Output “YES” if it is possible to reproduce the art piece, or “NO” otherwise.

-----Examples-----
Sample Input 1:
4 5
WRRRG
WRRRG
WRRRG
WBBBB
Sample Output 1:
YES

Sample Input 2:
3 4
WWRR
WRRR
WRRR
Sample Output 2:
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mia is a newly hired administrative assistant. Though Mia was introduced to everyone in the company on her first day, she is forgetful and struggles to remember people’s names. Being too shy to ask for names again, she discovers a way to recall people’s names during lunchtime without asking.

Mia orders lunch for all of her colleagues in each of the next several days. On any day, Mia orders burgers for some of her colleagues and salads for the rest of her colleagues. The number of burgers she orders may vary per day. After placing the order, she sends an email to the colleagues who get a burger for lunch, and also to the remaining colleagues about their salads. Mia has an email list with all her colleagues’ names. She may choose by name who gets a burger and who gets a salad. Mia can see her colleagues as they are eating their lunch. Thus, by observing who turns out to eat a burger in the office and who eats a salad, she may gain some information to help her uniquely identify the names of her colleagues.

For example, suppose there are three colleagues with names Alice, Danielle, and Jennifer, and Mia can order one burger plus two salads on each day. On the first day, if Mia orders a burger for Alice and salads for Danielle and Jennifer, she can then tell who is Alice by observing who eats a burger. On the second day, Mia may order a burger for Danielle and a salad for Jennifer (and a salad for Alice who is already identified). Consequently she can uniquely identify all three colleagues.

What is the maximum number of colleagues that Mia can uniquely identify in the next few days, if she allocates the burger and salad recipients optimally?

-----Input-----
The first line of input contains two space-separated integers $n$ ($2 \leq n \leq 30$) and $m$ ($1 \leq m \leq 10$), where Mia has $n$ colleagues and will be ordering lunch for $m$ days.

Each of the next $m$ lines contains a single integer $a$ ($1 \leq a < n$), which is the number of burgers Mia orders on that day. The days are listed in order.

-----Output-----
Output a single integer, which is the maximum number of Mia’s $n$ colleagues that she can uniquely identify after $m$ days.

-----Examples-----
Sample Input:
4 2
2
2
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a Singly Linked List of size N, delete all alternate nodes of the list.
Example 1:
Input:
LinkedList: 1->2->3->4->5->6
Output: 1->3->5
Explanation: Deleting alternate nodes
results in the linked list with elements
1->3->5.
 
Example 2:
Input:
LinkedList: 99->59->42->20
Output: 99->42
 
Your Task:
Your task is to complete the function deleteAlt() which takes the head of the linked list in the input parameter and modifies the given linked list accordingly.
 
Constraints:
1<=N<=100
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is an experienced participant in Codehorses programming contests. Now he wants to become a problemsetter.

He sent to the coordinator a set of n problems. Each problem has it's quality, the quality of the i-th problem is ai (ai can be positive, negative or equal to zero). The problems are ordered by expected difficulty, but the difficulty is not related to the quality in any way. The easiest problem has index 1, the hardest problem has index n.

The coordinator's mood is equal to q now. After reading a problem, the mood changes by it's quality. It means that after the coordinator reads a problem with quality b, the value b is added to his mood. The coordinator always reads problems one by one from the easiest to the hardest, it's impossible to change the order of the problems.

If after reading some problem the coordinator's mood becomes negative, he immediately stops reading and rejects the problemset.

Polycarp wants to remove the minimum number of problems from his problemset to make the coordinator's mood non-negative at any moment of time. Polycarp is not sure about the current coordinator's mood, but he has m guesses "the current coordinator's mood q = bi".

For each of m guesses, find the minimum number of problems Polycarp needs to remove so that the coordinator's mood will always be greater or equal to 0 while he reads problems from the easiest of the remaining problems to the hardest.

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 750, 1 ≤ m ≤ 200 000) — the number of problems in the problemset and the number of guesses about the current coordinator's mood.

The second line of input contains n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the qualities of the problems in order of increasing difficulty.

The third line of input contains m integers b1, b2, ..., bm (0 ≤ bi ≤ 1015) — the guesses of the current coordinator's mood q.

Output

Print m lines, in i-th line print single integer — the answer to the problem with q = bi.

Example

Input

6 3
8 -5 -4 1 -7 4
0 7 3


Output

2
0
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a special connected undirected graph where each vertex belongs to at most one simple cycle.

Your task is to remove as many edges as needed to convert this graph into a tree (connected graph with no cycles). 

For each node, independently, output the maximum distance between it and a leaf in the resulting tree, assuming you were to remove the edges in a way that minimizes this distance.

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 5⋅ 10^5), the number of nodes and the number of edges, respectively.

Each of the following m lines contains two integers u and v (1 ≤ u,v ≤ n, u ≠ v), and represents an edge connecting the two nodes u and v. Each pair of nodes is connected by at most one edge.

It is guaranteed that the given graph is connected and each vertex belongs to at most one simple cycle.

Output

Print n space-separated integers, the i-th integer represents the maximum distance between node i and a leaf if the removed edges were chosen in a way that minimizes this distance.

Examples

Input

9 10
7 2
9 2
1 6
3 1
4 3
4 7
7 6
9 8
5 8
5 9


Output

5 3 5 4 5 4 3 5 4


Input

4 4
1 2
2 3
3 4
4 1


Output

2 2 2 2

Note

In the first sample, a possible way to minimize the maximum distance from vertex 1 is by removing the marked edges in the following image:

<image>

Note that to minimize the answer for different nodes, you can remove different edges.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ksusha the Squirrel is standing at the beginning of a straight road, divided into *n* sectors. The sectors are numbered 1 to *n*, from left to right. Initially, Ksusha stands in sector 1. 

Ksusha wants to walk to the end of the road, that is, get to sector *n*. Unfortunately, there are some rocks on the road. We know that Ksusha hates rocks, so she doesn't want to stand in sectors that have rocks.

Ksusha the squirrel keeps fit. She can jump from sector *i* to any of the sectors *i*<=+<=1,<=*i*<=+<=2,<=...,<=*i*<=+<=*k*. 

Help Ksusha! Given the road description, say if she can reach the end of the road (note, she cannot stand on a rock)?

Input Specification:
The first line contains two integers *n* and *k* (2<=≤<=*n*<=≤<=3·105,<=1<=≤<=*k*<=≤<=3·105). The next line contains *n* characters — the description of the road: the *i*-th character equals ".", if the *i*-th sector contains no rocks. Otherwise, it equals "#".

It is guaranteed that the first and the last characters equal ".".

Output Specification:
Print "YES" (without the quotes) if Ksusha can reach the end of the road, otherwise print "NO" (without the quotes).

Demo Input:
['2 1\n..\n', '5 2\n.#.#.\n', '7 3\n.#.###.\n']

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

Note:
none

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

In the Demon's Plan, 108 demons who control the desire are competing in the programming contest day and night. The organizer, Patron, is trying to invite the demons to "Rix-Magna", a place where all the souls gather. Patron wants to send an invitation to a demon who hasn't sent an invitation yet, but he decides to let his familiars do it because the demons are all over the world and it's a hassle to go by himself. Patrons are smart and are trying to allocate which familiars are in charge of which demons so that the familiars work more equally.

Problem

There are N familiars and M demons. The distance between familiar i and devil j is Hi j.

I want each demon to have one familiar. Which familiar will visit which demon will be assigned according to the following conditions.

1. Minimize the maximum difference in the number of demons visited per familiar.
2. Minimize the maximum distance between the visiting demon and the familiar familiar after satisfying 1.



Output the maximum difference in the number of visiting demons per familiar on the first line, and the maximum distance between the demon and the familiar in charge on the second line.

Constraints

* 1 ≤ N ≤ 108
* 1 ≤ M ≤ 108
* 1 ≤ Hi j ≤ 109 (0 ≤ i <N, 0 ≤ j <M) (distance from familiar i to devil j)

Input

The input is given in the following format.


N M
H0 0 H0 1… H0 M−1
H1 0 H1 1… H1 M-1
..
..
HN−1 0 HN−1 1… HN−1 M−1


On the first line, the number N of familiars and the number M of demons are given as integers separated by blanks. The distance between the familiar and the devil is given as an integer in the following N lines. Hij represents the distance between familiar i and devil j.

Output

According to the conditions of the problem statement, output the maximum difference in the number of visiting demons per familiar on the first line, and the maximum distance between the demon and the familiar in charge on the second line.

Examples

Input

3 3
1 2 3
2 1 2
3 2 1


Output

0
1


Input

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


Output

1
2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
John Doe has a list of all Fibonacci numbers modulo 1013. This list is infinite, it starts with numbers 0 and 1. Each number in the list, apart from the first two, is a sum of previous two modulo 1013. That is, John's list is made from the Fibonacci numbers' list by replacing each number there by the remainder when divided by 1013. 

John got interested in number *f* (0<=≤<=*f*<=&lt;<=1013) and now wants to find its first occurrence in the list given above. Help John and find the number of the first occurence of number *f* in the list or otherwise state that number *f* does not occur in the list. 

The numeration in John's list starts from zero. There, the 0-th position is the number 0, the 1-st position is the number 1, the 2-nd position is the number 1, the 3-rd position is the number 2, the 4-th position is the number 3 and so on. Thus, the beginning of the list looks like this: 0,<=1,<=1,<=2,<=3,<=5,<=8,<=13,<=21,<=...

Input Specification:
The first line contains the single integer *f* (0<=≤<=*f*<=&lt;<=1013) — the number, which position in the list we should find.

Please, do not use 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 Specification:
Print a single number — the number of the first occurrence of the given number in John's list. If this number doesn't occur in John's list, print -1.

Demo Input:
['13\n', '377\n']

Demo Output:
['7\n', '14\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This kata is inspired on the problem #50 of the Project Euler. 

The prime ``` 41```  is the result of the sum of many consecutive primes.

In fact, ``` 2 + 3 + 5 + 7 + 11 + 13 = 41 , (6 addens)   ``` 

Furthermore, the prime ``` 41```  is the prime below ``` 100 (val_max)```  that has the longest chain of consecutive prime addens.

The prime with longest chain of addens for ```val_max = 500``` is ```499``` with ```17``` addens. 

In fact:
```3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61= 499```

Find the function ```prime_maxlength_chain()```(primeMaxlengthChain() javascript), that receives an argument ```val_max```, the upper limit, all the found primes should be less than ```val_max``` and outputs this found prime.

Let's see some cases:
```python
prime_maxlength_chain(100) == [41]
prime_maxlength_chain(500) == [499]
```
If we have more than one prime with these features, the function should output an array with the found primes sorted.
```python
prime_maxlength_chain(499) == [379, 491]
```
Random Tests for `val_max` (`valMax`)
```
100 ≤ val_max ≤ 500.000
```
Enjoy it!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Ivan bought a new computer. Excited, he unpacked it and installed his favourite game. With his old computer Ivan had to choose the worst possible graphic settings (because otherwise the framerate would be really low), but now he wants to check, maybe his new computer can perform well even with the best possible graphics?

There are m graphics parameters in the game. i-th parameter can be set to any positive integer from 1 to ai, and initially is set to bi (bi ≤ ai). So there are <image> different combinations of parameters. Ivan can increase or decrease any of these parameters by 1; after that the game will be restarted with new parameters (and Ivan will have the opportunity to check chosen combination of parameters).

Ivan wants to try all p possible combinations. Also he wants to return to the initial settings after trying all combinations, because he thinks that initial settings can be somehow best suited for his hardware. But Ivan doesn't really want to make a lot of restarts.

So he wants you to tell the following:

  * If there exists a way to make exactly p changes (each change either decreases or increases some parameter by 1) to try all possible combinations and return to initial combination, then Ivan wants to know this way. 
  * Otherwise, if there exists a way to make exactly p - 1 changes to try all possible combinations (including the initial one), then Ivan wants to know this way. 



Help Ivan by showing him the way to change parameters!

Input

The first line of input contains one integer number m (1 ≤ m ≤ 6).

The second line contains m integer numbers a1, a2, ..., am (2 ≤ ai ≤ 1000). It is guaranteed that <image>.

The third line contains m integer numbers b1, b2, ..., bm (1 ≤ bi ≤ ai).

Output

If there is a way to make exactly p changes (each change either decreases or increases some parameter by 1) to try all possible combinations and return to initial combination, then output Cycle in the first line. Then p lines must follow, each desribing a change. The line must be either inc x (increase parameter x by 1) or dec x (decrease it).

Otherwise, if there is a way to make exactly p - 1 changes to try all possible combinations (including the initial one), then output Path in the first line. Then p - 1 lines must follow, each describing the change the same way as mentioned above.

Otherwise, output No.

Examples

Input

1
3
1


Output

Path
inc 1
inc 1


Input

1
3
2


Output

No


Input

2
3 2
1 1


Output

Cycle
inc 1
inc 1
inc 2
dec 1
dec 1
dec 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, remove all its adjacent duplicate characters recursively. 
Note: For some test cases, the resultant string would be an empty string. In that case, the function should return the empty string only.
Example 1:
Input:
S = "geeksforgeek"
Output: "gksforgk"
Explanation: 
g(ee)ksforg(ee)k -> gksforgk
Example 2:
Input: 
S = "abccbccba"
Output: ""
Explanation: 
ab(cc)b(cc)ba->abbba->a(bbb)a->aa->(aa)->""(empty string)
Your Task:
You don't need to read input or print anything. Your task is to complete the function rremove() which takes the string S as input parameter and returns the resultant string.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1<=|S|<=10^{5}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given *n* integers *a*1,<=<=*a*2,<=<=...,<=<=*a**n*.

A sequence of integers *x*1,<=<=*x*2,<=<=...,<=<=*x**k* is called a "xor-sequence" if for every 1<=<=≤<=<=*i*<=<=≤<=<=*k*<=-<=1 the number of ones in the binary representation of the number *x**i*  *x**i*<=<=+<=<=1's is a multiple of 3 and  for all 1<=≤<=*i*<=≤<=*k*. The symbol  is used for the binary exclusive or operation.

How many "xor-sequences" of length *k* exist? Output the answer modulo 109<=+<=7.

Note if *a*<==<=[1,<=1] and *k*<==<=1 then the answer is 2, because you should consider the ones from *a* as different.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=100, 1<=≤<=*k*<=≤<=1018) — the number of given integers and the length of the "xor-sequences".

The second line contains *n* integers *a**i* (0<=≤<=*a**i*<=≤<=1018).

Output Specification:
Print the only integer *c* — the number of "xor-sequences" of length *k* modulo 109<=+<=7.

Demo Input:
['5 2\n15 1 2 4 8\n', '5 1\n15 1 2 4 8\n']

Demo Output:
['13\n', '5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have just been hired by Amalgamated, Inc. in the country of Acmania to oversee the transportation of raw materials to the company’s factories. Each supplier of raw materials and each factory resides in one of Acmania’s states. No state has both a factory and a supplier (and never more than one of either) and there are arcane laws governing which transportation companies can transport materials across state lines. Because of the fierce competition between factories and between suppliers each transportation company handles the output of at most one raw material site and delivers to at most one factory (or to another transportation company). Each supplier can produce enough material to contract with at most one factory and no factory will contract with more than one supplier. Your job is to determine the maximum number of factories that can be supplied with raw materials.

For example, suppose that there are three suppliers in states A, B and C, and three factories in states D, E and F. Let’s say you contract three transportation firms: firm $1$ can transport between states A, E and G; firm $2$ can transport between states A, C and E; and firm $3$ can transport between states B, D and F. In this case, you can supply at most two factories (for example, factory E can be supplied from supplier A using firm $1$, and factory F can be supplied from supplier B using firm $3$). If you find a fourth firm that transports between states G and F then you can supply all three factories: factory D can be supplied from B using firm $3$, factory E can be supplied from C using firm $2$, and factory F can be supplied from A using firms $1$ and $4$.

-----Input-----
The input will start with four positive integers $s$ $r$ $f$ $t$ indicating the number of states, raw material sites, factories and transportation companies, where $1 \leq r,f \leq 200$, $r+f \leq s \leq 600$ and $1 \leq t \leq 1000$.

Next will follow a line containing $r$ state names, one for each raw material site.

The next line will contain $f$ state names, one for each factory site.

Finally there will be $t$ lines, one for each transportation company. Each of these lines will start with an integer $n$, $1 \leq n \leq s$, indicating the number of states the company is allowed to work in, followed by $n$ state names. No state will contain both a raw material site and a factory site.

All state names will be alphabetic strings with no blanks.



-----Output-----
Output the maximum number of factories that can be supplied with raw materials.

-----Examples-----
Sample Input:
7 3 3 3
A B C
D E F
3 A E G
3 A C E
3 B D F
Sample Output:
2

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