vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Scientists say a lot about the problems of global warming and cooling of the Earth. Indeed, such natural phenomena strongly influence all life on our planet.

Our hero Vasya is quite concerned about the problems. He decided to try a little experiment and observe how outside daily temperature changes. He hung out a thermometer on the balcony every morning and recorded the temperature. He had been measuring the temperature for the last n days. Thus, he got a sequence of numbers t_1, t_2, ..., t_{n}, where the i-th number is the temperature on the i-th day.

Vasya analyzed the temperature statistics in other cities, and came to the conclusion that the city has no environmental problems, if first the temperature outside is negative for some non-zero number of days, and then the temperature is positive for some non-zero number of days. More formally, there must be a positive integer k (1 ≤ k ≤ n - 1) such that t_1 < 0, t_2 < 0, ..., t_{k} < 0 and t_{k} + 1 > 0, t_{k} + 2 > 0, ..., t_{n} > 0. In particular, the temperature should never be zero. If this condition is not met, Vasya decides that his city has environmental problems, and gets upset.

You do not want to upset Vasya. Therefore, you want to select multiple values of temperature and modify them to satisfy Vasya's condition. You need to know what the least number of temperature values needs to be changed for that.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of days for which Vasya has been measuring the temperature. 

The second line contains a sequence of n integers t_1, t_2, ..., t_{n} (|t_{i}| ≤ 10^9) — the sequence of temperature values. Numbers t_{i} are separated by single spaces.


-----Output-----

Print a single integer — the answer to the given task.


-----Examples-----
Input
4
-1 1 -2 1

Output
1

Input
5
0 -1 1 2 -5

Output
2



-----Note-----

Note to the first sample: there are two ways to change exactly one number so that the sequence met Vasya's condition. You can either replace the first number 1 by any negative number or replace the number -2 by any positive number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a forest — an undirected graph with n vertices such that each its connected component is a tree.

The diameter (aka "longest shortest path") of a connected undirected graph is the maximum number of edges in the shortest path between any pair of its vertices.

You task is to add some edges (possibly zero) to the graph so that it becomes a tree and the diameter of the tree is minimal possible.

If there are multiple correct answers, print any of them.

Input

The first line contains two integers n and m (1 ≤ n ≤ 1000, 0 ≤ m ≤ n - 1) — the number of vertices of the graph and the number of edges, respectively.

Each of the next m lines contains two integers v and u (1 ≤ v, u ≤ n, v ≠ u) — the descriptions of the edges.

It is guaranteed that the given graph is a forest.

Output

In the first line print the diameter of the resulting tree.

Each of the next (n - 1) - m lines should contain two integers v and u (1 ≤ v, u ≤ n, v ≠ u) — the descriptions of the added edges.

The resulting graph should be a tree and its diameter should be minimal possible.

For m = n - 1 no edges are added, thus the output consists of a single integer — diameter of the given tree.

If there are multiple correct answers, print any of them.

Examples

Input


4 2
1 2
2 3


Output


2
4 2


Input


2 0


Output


1
1 2


Input


3 2
1 3
2 3


Output


2

Note

In the first example adding edges (1, 4) or (3, 4) will lead to a total diameter of 3. Adding edge (2, 4), however, will make it 2.

Edge (1, 2) is the only option you have for the second example. The diameter is 1.

You can't add any edges in the third example. The diameter is already 2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's imagine that you're playing the following simple computer game. The screen displays *n* lined-up cubes. Each cube is painted one of *m* colors. You are allowed to delete not more than *k* cubes (that do not necessarily go one after another). After that, the remaining cubes join together (so that the gaps are closed) and the system counts the score. The number of points you score equals to the length of the maximum sequence of cubes of the same color that follow consecutively. Write a program that determines the maximum possible number of points you can score.

Remember, you may delete no more than *k* any cubes. It is allowed not to delete cubes at all.

Input Specification:
The first line contains three integers *n*, *m* and *k* (1<=≤<=*n*<=≤<=2·105,<=1<=≤<=*m*<=≤<=105,<=0<=≤<=*k*<=&lt;<=*n*). The second line contains *n* integers from 1 to *m* — the numbers of cube colors. The numbers of colors are separated by single spaces.

Output Specification:
Print the maximum possible number of points you can score.

Demo Input:
['10 3 2\n1 2 1 1 3 2 1 1 2 2\n', '10 2 2\n1 2 1 2 1 1 2 1 1 2\n', '3 1 2\n1 1 1\n']

Demo Output:
['4\n', '5\n', '3\n']

Note:
In the first sample you should delete the fifth and the sixth cubes.

In the second sample you should delete the fourth and the seventh cubes.

In the third sample you shouldn't delete any cubes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an airplane which has n rows from front to back. There will be m people boarding this airplane.

This airplane has an entrance at the very front and very back of the plane.

Each person has some assigned seat. It is possible for multiple people to have the same assigned seat. The people will then board the plane one by one starting with person 1. Each person can independently choose either the front entrance or back entrance to enter the plane.

When a person walks into the plane, they walk directly to their assigned seat and will try to sit in it. If it is occupied, they will continue walking in the direction they walked in until they are at empty seat - they will take the earliest empty seat that they can find. If they get to the end of the row without finding a seat, they will be angry.

Find the number of ways to assign tickets to the passengers and board the plane without anyone getting angry. Two ways are different if there exists a passenger who chose a different entrance in both ways, or the assigned seat is different. Print this count modulo 10^9 + 7.


-----Input-----

The first line of input will contain two integers n, m (1 ≤ m ≤ n ≤ 1 000 000), the number of seats, and the number of passengers, respectively.


-----Output-----

Print a single number, the number of ways, modulo 10^9 + 7.


-----Example-----
Input
3 3

Output
128



-----Note-----

Here, we will denote a passenger by which seat they were assigned, and which side they came from (either "F" or "B" for front or back, respectively).

For example, one valid way is 3B, 3B, 3B (i.e. all passengers were assigned seat 3 and came from the back entrance). Another valid way would be 2F, 1B, 3F.

One invalid way would be 2B, 2B, 2B, since the third passenger would get to the front without finding a seat.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a string S of length N consisting of characters 0 and 1. You will perform the following operation for each i = 1, 2, ..., m:
 - Arbitrarily permute the characters within the substring of S starting at the l_i-th character from the left and extending through the r_i-th character.
Here, the sequence l_i is non-decreasing.
How many values are possible for S after the M operations, modulo 1000000007(= 10^9+7)?

-----Constraints-----
 - 2≦N≦3000
 - 1≦M≦3000
 - S consists of characters 0 and 1.
 - The length of S equals N.
 - 1≦l_i < r_i≦N
 - l_i ≦ l_{i+1}

-----Input-----
The input is given from Standard Input in the following format:
N M
S
l_1 r_1
:
l_M r_M

-----Output-----
Print the number of the possible values for S after the M operations, modulo 1000000007.

-----Sample Input-----
5 2
01001
2 4
3 5

-----Sample Output-----
6

After the first operation, S can be one of the following three: 01001, 00101 and 00011.
After the second operation, S can be one of the following six: 01100, 01010, 01001, 00011, 00101 and 00110.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kefa decided to celebrate his first big salary by going to the restaurant. 

He lives by an unusual park. The park is a rooted tree consisting of n vertices with the root at vertex 1. Vertex 1 also contains Kefa's house. Unfortunaely for our hero, the park also contains cats. Kefa has already found out what are the vertices with cats in them.

The leaf vertices of the park contain restaurants. Kefa wants to choose a restaurant where he will go, but unfortunately he is very afraid of cats, so there is no way he will go to the restaurant if the path from the restaurant to his house contains more than m consecutive vertices with cats. 

Your task is to help Kefa count the number of restaurants where he can go.


-----Input-----

The first line contains two integers, n and m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ n) — the number of vertices of the tree and the maximum number of consecutive vertices with cats that is still ok for Kefa.

The second line contains n integers a_1, a_2, ..., a_{n}, where each a_{i} either equals to 0 (then vertex i has no cat), or equals to 1 (then vertex i has a cat).

Next n - 1 lines contains the edges of the tree in the format "x_{i} y_{i}" (without the quotes) (1 ≤ x_{i}, y_{i} ≤ n, x_{i} ≠ y_{i}), where x_{i} and y_{i} are the vertices of the tree, connected by an edge. 

It is guaranteed that the given set of edges specifies a tree.


-----Output-----

A single integer — the number of distinct leaves of a tree the path to which from Kefa's home contains at most m consecutive vertices with cats.


-----Examples-----
Input
4 1
1 1 0 0
1 2
1 3
1 4

Output
2

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

Output
2



-----Note-----

Let us remind you that a tree is a connected graph on n vertices and n - 1 edge. A rooted tree is a tree with a special vertex called root. In a rooted tree among any two vertices connected by an edge, one vertex is a parent (the one closer to the root), and the other one is a child. A vertex is called a leaf, if it has no children.

Note to the first sample test: $80$ The vertices containing cats are marked red. The restaurants are at vertices 2, 3, 4. Kefa can't go only to the restaurant located at vertex 2.

Note to the second sample test: $88$ The restaurants are located at vertices 4, 5, 6, 7. Kefa can't go to restaurants 6, 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You read scientific research regarding popularity of most famous superstitions across various countries, and you want to analyze their data. More specifically, you want to know which superstitions are popular in most countries.

The data is given as a single file in the following format: country name on a separate line, followed by a list of superstitions popular in it, one entry per line. Each entry of the list is formatted as an asterisk "*" followed by a single space and then by the superstition name. Entries are unique within each country. The first line of input will represent a country. The input will contain at least one superstition. 

Country name is a non-empty sequence of words, where each word consists of only English letters. The words of the name of some country will be separated in input with one or more spaces.

Superstition name is a non-empty sequence of words, where each word consists of only English letters and digits. The words of the name of some superstition will be separated in input with one or more spaces.

You can consider two names equal, if corresponding sequences of words are equal. You shouldn't consider the case of the letters when you compare the words.

Output the list of superstitions which are observed in the greatest number of countries. It's guaranteed that all countries have distinct names.

Input

The input contains between 2 and 50 lines. Every line of input will contain between 1 and 50 characters, inclusive.

No line has leading or trailing spaces.

Output

Output the list of superstitions which are observed in the greatest number of countries in alphabetical order. Each superstition must be converted to lowercase (one superstition can be written with varying capitalization in different countries).

The alphabetical order of superstitions means the lexicographical order of sequences of words (their names).

Examples

Input

Ukraine
* Friday the   13th
* black   cat
* knock the   wood
USA
* wishing well
* friday   the   13th
Holland
France
* Wishing Well


Output

friday the 13th 
wishing well 


Input

Spain
* Tuesday the 13th
Italy
* Friday the 17th
Russia
* Friday the 13th
England
* rabbit foot


Output

friday the 13th 
friday the 17th 
rabbit foot 
tuesday the 13th 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
John likes simple ciphers. He had been using the “Caesar” cipher to encrypt his diary until recently, when he learned a hard lesson about its strength by catching his sister Mary browsing through the diary without any problems.

Rapidly searching for an alternative, John found a solution: the famous “Autokey” cipher. He uses a version that takes the $26$ lower-case letters ‘a’–‘z’ and internally translates them in alphabetical order to the numbers $0$ to $25$.

The encryption key $k$ begins with a secret prefix of $n$ letters. Each of the remaining letters of the key is copied from the letters of the plaintext $a$, so that $k_{n+i} = a_{i}$ for $i \geq 1$. Encryption of the plaintext $a$ to the ciphertext $b$ follows the formula $b_ i = a_ i + k_ i \bmod 26$.

Mary is not easily discouraged. She was able to get a peek at the last $n$ letters John typed into his diary on the family computer before he noticed her, quickly encrypted the text document with a click, and left. This could be her chance.

-----Input-----
The input consists of:
 - One line with two integers $n$ and $m$ ($1 \le n \le 30$, $n + 1 \le m \le 100$), where $n$ is the length of the keyword as well as the number of letters Mary saw, and $m$ is the length of the text.
 - One line with $n$ lower-case letters, the last $n$ letters of the plaintext.
 - One line with $m$ lower-case letters, the whole ciphertext.

-----Output-----
Output the plaintext of John’s diary.

-----Examples-----
Sample Input:
5 16
again
pirpumsemoystoal
Sample Output:
marywasnosyagain

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have two arrays A and B of size N and M respectively. You have to merge both the arrays to form a new array C of size N + M (the relative order of elements in the original arrays A and B should not change in the array C).

For e.g. if A = [{\color{blue}1}, {\color{blue}2}, {\color{blue}7} ] and B = [{\color{red}3}, {\color{red}6}, {\color{red}5}], one possible way to merge them to form C is: C = [{\color{blue}1}, {\color{red}3}, {\color{red}6}, {\color{blue}2}, {\color{red}5}, {\color{blue}7}].

Maximize the length of longest non-decreasing subsequence of the merged array C.

As a reminder, a non-decreasing subsequence of some array X is a sequence of indices i_{1}, i_{2}, ..., i_{k}, such that i_{1} < i_{2} < ... < i_{k} and X_{i_{1}} ≤ X_{i_{2}} ≤ ... ≤ X_{i_{k}}

------ Input Format ------ 

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and M - the size of the array A and B respectively.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.
- The third line of each test case contains M space-separated integers B_{1}, B_{2}, \dots, B_{M} denoting the array B.

------ Output Format ------ 

For each test case, output the maximum possible length of longest non-decreasing subsequence in the merged array.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N, M ≤ 10^{5}$ 
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $4 \cdot 10^{5}$.
- It is guaranteed that the sum of $M$ over all test cases does not exceed $4 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
3 2
6 4 5
1 3
2 3
1 3
2 2 4

----- Sample Output 1 ------ 
4
5

----- explanation 1 ------ 
Test Case-1: We can merge the arrays in the following way: $C = [{\color{blue}6}, {\color{red}1}, {\color{red}3}, {\color{blue}4}, {\color{blue}5}]$. The length of longest non-decreasing subsequence in this case is $4$.

Test Case-2: We can merge the arrays in the following way: $C = [{\color{blue}1}, {\color{red}2}, {\color{red}2}, {\color{blue}3}, {\color{red}4}]$. The length of longest non-decreasing subsequence in this case is $5$.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
A number is called almost prime if it has exactly two distinct prime divisors. For example, numbers 6, 18, 24 are almost prime, while 4, 8, 9, 42 are not. Find the amount of almost prime numbers which are between 1 and *n*, inclusive.

Input Specification:
Input contains one integer number *n* (1<=≤<=*n*<=≤<=3000).

Output Specification:
Output the amount of almost prime numbers between 1 and *n*, inclusive.

Demo Input:
['10\n', '21\n']

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A country has *n* cities. Initially, there is no road in the country. One day, the king decides to construct some roads connecting pairs of cities. Roads can be traversed either way. He wants those roads to be constructed in such a way that it is possible to go from each city to any other city by traversing at most two roads. You are also given *m* pairs of cities — roads cannot be constructed between these pairs of cities.

Your task is to construct the minimum number of roads that still satisfy the above conditions. The constraints will guarantee that this is always possible.

Input Specification:
The first line consists of two integers *n* and *m* .

Then *m* lines follow, each consisting of two integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*, *a**i*<=≠<=*b**i*), which means that it is not possible to construct a road connecting cities *a**i* and *b**i*. Consider the cities are numbered from 1 to *n*.

It is guaranteed that every pair of cities will appear at most once in the input.

Output Specification:
You should print an integer *s*: the minimum number of roads that should be constructed, in the first line. Then *s* lines should follow, each consisting of two integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*), which means that a road should be constructed between cities *a**i* and *b**i*.

If there are several solutions, you may print any of them.

Demo Input:
['4 1\n1 3\n']

Demo Output:
['3\n1 2\n4 2\n2 3\n']

Note:
This is one possible solution of the example: 

These are examples of wrong solutions:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer x, find 2 integers a and b such that: 

  * 1 ≤ a,b ≤ x 
  * b divides a (a is divisible by b). 
  * a ⋅ b>x. 
  * a/b<x. 

Input

The only line contains the integer x (1 ≤ x ≤ 100).

Output

You should output two integers a and b, satisfying the given conditions, separated by a space. If no pair of integers satisfy the conditions above, print "-1" (without quotes).

Examples

Input

10


Output

6 3

Input

1


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.
A subarray of an array is a consecutive sequence of zero or more values taken out of that array.
Return the maximum length of a subarray with positive product.
 
Example 1:
Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:
Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.
Example 3:
Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Example 4:
Input: nums = [-1,2]
Output: 1

Example 5:
Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4

 
Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's call a number *k*-good if it contains all digits not exceeding *k* (0,<=...,<=*k*). You've got a number *k* and an array *a* containing *n* numbers. Find out how many *k*-good numbers are in *a* (count each number every time it occurs in array *a*).

Input Specification:
The first line contains integers *n* and *k* (1<=≤<=*n*<=≤<=100, 0<=≤<=*k*<=≤<=9). The *i*-th of the following *n* lines contains integer *a**i* without leading zeroes (1<=≤<=*a**i*<=≤<=109).

Output Specification:
Print a single integer — the number of *k*-good numbers in *a*.

Demo Input:
['10 6\n1234560\n1234560\n1234560\n1234560\n1234560\n1234560\n1234560\n1234560\n1234560\n1234560\n', '2 1\n1\n10\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$. You have to reverse it — that is, the first letter should become equal to the last letter before the reversal, the second letter should become equal to the second-to-last letter before the reversal — and so on. For example, if your goal is to reverse the string "abddea", you should get the string "aeddba". To accomplish your goal, you can swap the neighboring elements of the string. 

Your task is to calculate the minimum number of swaps you have to perform to reverse the given string.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 200\,000$) — the length of $s$.

The second line contains $s$ — a string consisting of $n$ lowercase Latin letters.


-----Output-----

Print one integer — the minimum number of swaps of neighboring elements you have to perform to reverse the string.


-----Examples-----
Input
5
aaaza

Output
2

Input
6
cbaabc

Output
0

Input
9
icpcsguru

Output
30



-----Note-----

In the first example, you have to swap the third and the fourth elements, so the string becomes "aazaa". Then you have to swap the second and the third elements, so the string becomes "azaaa". So, it is possible to reverse the string in two swaps.

Since the string in the second example is a palindrome, you don't have to do anything to reverse it.

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