vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are n cities in the country of Berland. Some of them are connected by bidirectional roads in such a way that there exists exactly one path, which visits each road no more than once, between every pair of cities. Each road has its own length. Cities are numbered from 1 to n.

The travelling time between some cities v and u is the total length of the roads on the shortest path from v to u. 

The two most important cities in Berland are cities 1 and n.

The Berland Ministry of Transport decided to build a single new road to decrease the traffic between the most important cities. However, lots of people are used to the current travelling time between the most important cities, so the new road shouldn't change it too much. 

The new road can only be built between such cities v and u that v ≠ u and v and u aren't already connected by some road.

They came up with m possible projects. Each project is just the length x of the new road.

Polycarp works as a head analyst at the Berland Ministry of Transport and it's his job to deal with all those m projects. For the i-th project he is required to choose some cities v and u to build the new road of length x_i between such that the travelling time between the most important cities is maximal possible. 

Unfortunately, Polycarp is not a programmer and no analyst in the world is capable to process all projects using only pen and paper. 

Thus, he asks you to help him to calculate the maximal possible travelling time between the most important cities for each project. Note that the choice of v and u can differ for different projects.

Input

The first line contains two integers n and m (3 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ m ≤ 3 ⋅ 10^5) — the number of cities and the number of projects, respectively.

Each of the next n - 1 lines contains three integers v_i, u_i and w_i (1 ≤ v_i, u_i ≤ n, 1 ≤ w_i ≤ 10^9) — the description of the i-th road. It is guaranteed that there exists exactly one path, which visits each road no more than once, between every pair of cities.

Each of the next m lines contains a single integer x_j (1 ≤ x_j ≤ 10^9) — the length of the road for the j-th project.

Output

Print m lines, the j-th line should contain a single integer — the maximal possible travelling time between the most important cities for the j-th project.

Example

Input

7 2
1 2 18
2 3 22
3 4 24
4 7 24
2 6 4
3 5 12
1
100


Output

83
88

Note

The road network from the first example:

<image>

You can build the road with length 1 between cities 5 and 6 to get 83 as the travelling time between 1 and 7 (1 → 2 → 6 → 5 → 3 → 4 → 7 = 18 + 4 + 1 + 12 + 24 + 24 = 83). Other possible pairs of cities will give answers less or equal to 83.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Chubby Yang is studying linear equations right now. He came up with a nice problem. In the problem you are given an *n*<=×<=*n* matrix *W*, consisting of integers, and you should find two *n*<=×<=*n* matrices *A* and *B*, all the following conditions must hold: 
 -  *A**ij*<==<=*A**ji*, for all *i*,<=*j* (1<=≤<=*i*,<=*j*<=≤<=*n*); -  *B**ij*<==<=<=-<=*B**ji*, for all *i*,<=*j* (1<=≤<=*i*,<=*j*<=≤<=*n*); -  *W**ij*<==<=*A**ij*<=+<=*B**ij*, for all *i*,<=*j* (1<=≤<=*i*,<=*j*<=≤<=*n*). 
Can you solve the problem?

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=170). Each of the following *n* lines contains *n* integers. The *j*-th integer in the *i*-th line is *W**ij* (0<=≤<=|*W**ij*|<=&lt;<=1717).

Output Specification:
The first *n* lines must contain matrix *A*. The next *n* lines must contain matrix *B*. Print the matrices in the format equal to format of matrix *W* in input. It is guaranteed that the answer exists. If there are multiple answers, you are allowed to print any of them.

The answer will be considered correct if the absolute or relative error doesn't exceed 10<=-<=4.

Demo Input:
['2\n1 4\n3 2\n', '3\n1 2 3\n4 5 6\n7 8 9\n']

Demo Output:
['1.00000000 3.50000000\n3.50000000 2.00000000\n0.00000000 0.50000000\n-0.50000000 0.00000000\n', '1.00000000 3.00000000 5.00000000\n3.00000000 5.00000000 7.00000000\n5.00000000 7.00000000 9.00000000\n0.00000000 -1.00000000 -2.00000000\n1.00000000 0.00000000 -1.00000000\n2.00000000 1.00000000 0.00000000\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Vasily the Bear and Sequence

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasily the bear has got a sequence of positive integers *a*1,<=*a*2,<=...,<=*a**n*. Vasily the Bear wants to write out several numbers on a piece of paper so that the beauty of the numbers he wrote out was maximum. 

The beauty of the written out numbers *b*1,<=*b*2,<=...,<=*b**k* is such maximum non-negative integer *v*, that number *b*1 *and* *b*2 *and* ... *and* *b**k* is divisible by number 2*v* without a remainder. If such number *v* doesn't exist (that is, for any non-negative integer *v*, number *b*1 *and* *b*2 *and* ... *and* *b**k* is divisible by 2*v* without a remainder), the beauty of the written out numbers equals -1. 

Tell the bear which numbers he should write out so that the beauty of the written out numbers is maximum. If there are multiple ways to write out the numbers, you need to choose the one where the bear writes out as many numbers as possible.

Here expression *x* *and* *y* means applying the bitwise AND operation to numbers *x* and *y*. In programming languages C++ and Java this operation is represented by "&amp;", in Pascal — by "and".

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105). The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a*1<=&lt;<=*a*2<=&lt;<=...<=&lt;<=*a**n*<=≤<=109).

Output Specification:
In the first line print a single integer *k* (*k*<=&gt;<=0), showing how many numbers to write out. In the second line print *k* integers *b*1,<=*b*2,<=...,<=*b**k* — the numbers to write out. You are allowed to print numbers *b*1,<=*b*2,<=...,<=*b**k* in any order, but all of them must be distinct. If there are multiple ways to write out the numbers, choose the one with the maximum number of numbers to write out. If there still are multiple ways, you are allowed to print any of them.

Demo Input:
['5\n1 2 3 4 5\n', '3\n1 2 4\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set A containing n integers from 1 to n; A = {1,2,3,...n}. 

Let's call P(A) as a set that contains all permutations of A; 

For eg: if A = {1,2}. P(A) = {{1,2},{2,1}}

Can you find the number of elements a ∈ P(A) which satisfies following conditions:

For every 1 <= i <= n, a[i] ≠ i where a[i] is the i^{th} integer in permutation a
There exists a set of k integers {i_{1}, i_{2}, i_{3}, .... i_{k}} such that 
a[i_{j}] = i_{j+1} ∀ j < k and a[i_{k}] = i1 (cyclic)

Input Format 

The first line contains an integer T indicating the number of test-cases.
T lines follow. Each line has two integers n and k separated by a single space.

Constraints 

1 <= T <= 100 

1 <= k <= n <= 10^{6}

Output Format 

Output the remainder of the answer after divided by 1000000007 ie., (10^{9}+7)

Sample Input

4
3 2
4 2
5 3
6 2

Sample Output

0
3
20
105

Hint

10^{9}+7 is a prime number.

Explanation

note : Array's are 1 indexed. 

Lets take a look at N = 3 and K = 2

We will get 2 sets of A that satisfy the first property a[i] ≠ i, they are 

[3,1,2]
[2,3,1]

Now, as K = 2, we can have 6 such elements. 

[1,2], [1,3],[2,3], [2,1], [3,1], [3,2]

Lets consider the first element of P(A) -> [3,1,2] 

[1,2], a[1] ≠ 2
[1,3], a[1] = 3 but a[3] ≠ 1
[2,3], a[2] ≠ 3
[2,1], a[2] = 1 but a[1] ≠ 2
[3,1], a[3] = 1 but a[1] ≠ 3
[3,2], a[3] ≠ 2

Lets consider the second element of P(A) -> [2,3,1]

[1,2], a[1] = 2 but a[2] ≠ 1
[1,3], a[1] ≠ 3
[2,3], a[2] = 3 but a[3] ≠ 3
[2,1], a[2] ≠ 1
[3,1], a[3] = but a[1] ≠ 3
[3,2], a[3] ≠ 2

As none of the elements of a satisfy the properties above, hence 0. 

In the second case, n=4,k=2. Here follows all the permutations of 

A={1,2,3,4} we could find that satisfy the two condition above.

2 1 4 3 # (a[2] = 1, a[1] = 2) or (a[4] = 3, a[3] = 4) is ok.

4 3 2 1 # (a[4] = 1, a[1] = 4) or (a[3] = 2, a[2] = 3) is ok.

3 4 1 2 # (a[3] = 1, a[1] = 3) or (a[4] = 2, a[2] = 4) is ok.

Timelimits
Timelimits for this challenge is given here

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The problem uses a simplified TCP/IP address model, please make sure you've read the statement attentively.

Polycarpus has found a job, he is a system administrator. One day he came across n IP addresses. Each IP address is a 32 bit number, represented as a group of four 8-bit numbers (without leading zeroes), separated by dots. For example, the record 0.255.1.123 shows a correct IP address and records 0.256.1.123 and 0.255.1.01 do not. In this problem an arbitrary group of four 8-bit numbers is a correct IP address.

Having worked as an administrator for some time, Polycarpus learned that if you know the IP address, you can use the subnet mask to get the address of the network that has this IP addess.

The subnet mask is an IP address that has the following property: if we write this IP address as a 32 bit string, that it is representable as "11...11000..000". In other words, the subnet mask first has one or more one bits, and then one or more zero bits (overall there are 32 bits). For example, the IP address 2.0.0.0 is not a correct subnet mask as its 32-bit record looks as 00000010000000000000000000000000.

To get the network address of the IP address, you need to perform the operation of the bitwise "and" of the IP address and the subnet mask. For example, if the subnet mask is 255.192.0.0, and the IP address is 192.168.1.2, then the network address equals 192.128.0.0. In the bitwise "and" the result has a bit that equals 1 if and only if both operands have corresponding bits equal to one.

Now Polycarpus wants to find all networks to which his IP addresses belong. Unfortunately, Polycarpus lost subnet mask. Fortunately, Polycarpus remembers that his IP addresses belonged to exactly k distinct networks. Help Polycarpus find the subnet mask, such that his IP addresses will belong to exactly k distinct networks. If there are several such subnet masks, find the one whose bit record contains the least number of ones. If such subnet mask do not exist, say so.


-----Input-----

The first line contains two integers, n and k (1 ≤ k ≤ n ≤ 10^5) — the number of IP addresses and networks. The next n lines contain the IP addresses. It is guaranteed that all IP addresses are distinct.


-----Output-----

In a single line print the IP address of the subnet mask in the format that is described in the statement, if the required subnet mask exists. Otherwise, print -1.


-----Examples-----
Input
5 3
0.0.0.1
0.1.1.2
0.0.2.1
0.1.1.0
0.0.2.3

Output
255.255.254.0
Input
5 2
0.0.0.1
0.1.1.2
0.0.2.1
0.1.1.0
0.0.2.3

Output
255.255.0.0
Input
2 1
255.0.0.1
0.0.0.2

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to Combine two Strings. But consider the rule...

By the way you don't have to check errors or incorrect input values, everything is ok without bad tricks, only two input strings and as result one output string;-)...

And here's the rule:  
Input Strings `a` and `b`: For every character in string `a` swap the casing of every occurrence of the same character in string `b`. Then do the same casing swap with the inputs reversed. Return a single string consisting of the changed version of `a` followed by the changed version of `b`. A char of `a` is in `b` regardless if it's in upper or lower case - see the testcases too.  
I think that's all;-)...

Some easy examples:

````
Input: "abc" and "cde"      => Output: "abCCde" 
Input: "ab" and "aba"       => Output: "aBABA"
Input: "abab" and "bababa"  => Output: "ABABbababa"
````

Once again for the last example - description from `KenKamau`, see discourse;-):

a) swap the case of characters in string `b` for every occurrence of that character in string `a`  
char `'a'` occurs twice in string `a`, so we swap all `'a'` in string `b` twice. This means we start with `"bababa"` then `"bAbAbA"` => `"bababa"`  
char `'b'` occurs twice in string `a` and so string `b` moves as follows: start with `"bababa"` then `"BaBaBa"` => `"bababa"`

b) then, swap the case of characters in string `a` for every occurrence in string `b`  
char `'a'` occurs `3` times in string `b`. So string `a` swaps cases as follows: start with `"abab"` then => `"AbAb"` => `"abab"` => `"AbAb"`  
char `'b'` occurs `3` times in string `b`. So string `a` swaps as follow: start with `"AbAb"` then => `"ABAB"` => `"AbAb"` => `"ABAB"`.

c) merge new strings `a` and `b`  
return `"ABABbababa"`

There are some static tests at the beginning and many random tests if you submit your solution.

Hope you have fun:-)!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lexicographical order is often known as alphabetical order when dealing with strings.  A string is greater than another string if it comes later in a lexicographically sorted list.

Given a word, create a new word by swapping some or all of its characters.  This new word must meet two criteria:

It must be greater than the original word
It must be the smallest word that meets the first condition

Example 

$w=\textbf{abcd}$

The next largest word is $\textbf{abdc}$.  

Complete the function biggerIsGreater below to create and return the new string meeting the criteria.  If it is not possible, return no answer.

Function Description  

Complete the biggerIsGreater function in the editor below.  

biggerIsGreater has the following parameter(s):  

string w: a word

Returns 

- string: the smallest lexicographically higher string possible or no answer  

Input Format

The first line of input contains $\mathbf{T}$, the number of test cases. 

Each of the next $\mathbf{T}$ lines contains $\boldsymbol{w}$.

Constraints

$1\leq T\leq10^5$  
$1\leq length of w\leq100$  
$\boldsymbol{w}$ will contain only letters in the range ascii[a..z].

Sample Input 0
5
ab
bb
hefg
dhck
dkhc

Sample Output 0
ba
no answer
hegf
dhkc
hcdk

Explanation 0

Test case 1: 

ba is the only string which can be made by rearranging ab. It is greater.   
Test case 2: 

It is not possible to rearrange bb and get a greater string.  
Test case 3: 

hegf is the next string greater than hefg.
Test case 4: 

dhkc is the next string greater than dhck.
Test case 5: 

hcdk is the next string greater than dkhc.

Sample Input 1
6
lmno
dcba
dcbb
abdc
abcd
fedcbabcd

Sample Output 1
lmon
no answer
no answer
acbd
abdc
fedcbabdc

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

Problem Statement

Given the string S. The following processing is performed in the order of Q pieces.

* Replace all the characters c_i contained in S with the character string p_i at the same time.



Finally, output (1-indexed) from the A character to the B character of the character string S.

Constraints

* 1 ≤ Q ≤ 3 \ times 10 ^ 5
* 1 ≤ A ≤ B ≤ 10 ^ {18}
* B-A ≤ 10 ^ 5
* 1 ≤ | S | ≤ 10
* 1 ≤ | p_i | ≤ 10
* S is a character string consisting of lowercase alphabets.
* c_i is one lowercase alphabetic character.
* p_i is a string consisting of one "." (Period) or a lowercase alphabet. When p_i = "." (Period), treat p_i as an empty string.

Input

Input follows the following format. All given numbers are integers.


S
Q A B
c_1 p_1
...
c_Q p_Q

Output

After performing Q processes in order, if B is larger than | S |, output "." (Period) on one line.
In other cases, output (1-indexed) from the A character to the B character of the character string S.

Examples

Input

abaz
3 1 5
a cab
b .
c x


Output

xaxaz


Input

original
1 2 5
x notchange


Output

rigi


Input

aaaa
2 1 1
a .
a nothing


Output

.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Longest k-Good Segment

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The array *a* with *n* integers is given. Let's call the sequence of one or more consecutive elements in *a* segment. Also let's call the segment k-good if it contains no more than *k* different values.

Find any longest k-good segment.

As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input Specification:
The first line contains two integers *n*,<=*k* (1<=≤<=*k*<=≤<=*n*<=≤<=5·105) — the number of elements in *a* and the parameter *k*.

The second line contains *n* integers *a**i* (0<=≤<=*a**i*<=≤<=106) — the elements of the array *a*.

Output Specification:
Print two integers *l*,<=*r* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*) — the index of the left and the index of the right ends of some k-good longest segment. If there are several longest segments you can print any of them. The elements in *a* are numbered from 1 to *n* from left to right.

Demo Input:
['5 5\n1 2 3 4 5\n', '9 3\n6 5 1 2 3 2 1 4 5\n', '3 1\n1 2 3\n']

Demo Output:
['1 5\n', '3 7\n', '1 1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I have an undirected graph consisting of n nodes, numbered 1 through n. Each node has at most two incident edges. For each pair of nodes, there is at most an edge connecting them. No edge connects a node to itself.

I would like to create a new graph in such a way that: 

  * The new graph consists of the same number of nodes and edges as the old graph. 
  * The properties in the first paragraph still hold. 
  * For each two nodes u and v, if there is an edge connecting them in the old graph, there is no edge connecting them in the new graph. 



Help me construct the new graph, or tell me if it is impossible.

Input

The first line consists of two space-separated integers: n and m (1 ≤ m ≤ n ≤ 105), denoting the number of nodes and edges, respectively. Then m lines follow. Each of the m lines consists of two space-separated integers u and v (1 ≤ u, v ≤ n; u ≠ v), denoting an edge between nodes u and v.

Output

If it is not possible to construct a new graph with the mentioned properties, output a single line consisting of -1. Otherwise, output exactly m lines. Each line should contain a description of edge in the same way as used in the input format.

Examples

Input

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


Output

1 4
4 6
1 6
2 7
7 5
8 5
2 8


Input

3 2
1 2
2 3


Output

-1


Input

5 4
1 2
2 3
3 4
4 1


Output

1 3
3 5
5 2
2 4

Note

The old graph of the first example:

<image>

A possible new graph for the first example:

<image>

In the second example, we cannot create any new graph.

The old graph of the third example:

<image>

A possible new graph for the third example:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Its Sparsh(Techno-cultural fest of SVNIT) time and committee of Sparsh is  getting ready in making college look clean and green ( :p ). As a part of it, they are decorating departments and roads of SVNIT with plant pots available in nursery of college.

There are N plant pots available in nursery placed in a straight line. Sparsh committee is planning to take few of these pots to keep in different places all over campus. But as nursery also being favorite place of love birds in college, the committee members do not want the nursery to look empty. So they thought that whatever number of pots they are going to take, they will take no two successive pots.(i.e. if they are taking a pot i from nursery, they will not take i-1 and i+1 pots.)

So given N, calculate how many different set of pots they could select. They need to take at least one pot from nursery.
Input:
First line contains number of test cases T.
Next T lines contain a single integer N each.

Output:
Print answer for each test case modulo 10^9 + 7. For each test case print in a new line.

Constraints:
1 < T < 1000000
2 < N < 1000000

Problem Setter : Vinay Kumar

SAMPLE INPUT
2
3
2

SAMPLE OUTPUT
4
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Beautiful Pairs of Numbers

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The sequence of integer pairs (*a*1,<=*b*1),<=(*a*2,<=*b*2),<=...,<=(*a**k*,<=*b**k*) is beautiful, if the following statements are fulfilled: 
 -  1<=≤<=*a*1<=≤<=*b*1<=&lt;<=*a*2<=≤<=*b*2<=&lt;<=...<=&lt;<=*a**k*<=≤<=*b**k*<=≤<=*n*, where *n* is a given positive integer; -  all numbers *b*1<=-<=*a*1, *b*2<=-<=*a*2, ..., *b**k*<=-<=*a**k* are distinct. 
For the given number *n* find the number of beautiful sequences of length *k*. As the answer can be rather large, print the remainder after dividing it by 1000000007 (109<=+<=7).

Input Specification:
The first line contains integer *t* (1<=≤<=*t*<=≤<=<=2·105) — the number of the test data.

Each of the next *t* lines contains two integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=1000).

Output Specification:
For each test from the input print the answer to the problem modulo 1000000007 (109<=+<=7). Print the answers to the tests in the order in which the tests are given in the input.

Demo Input:
['6\n1 1\n2 1\n2 2\n3 1\n3 2\n3 3\n']

Demo Output:
['1\n3\n0\n6\n2\n0\n']

Note:
In the first test sample there is exactly one beautiful sequence: (1, 1).

In the second test sample, the following sequences are beautiful: 
 -  (1, 1); -  (1, 2); -  (2, 2). 
In the fourth test sample, the following sequences are beautiful: 
 -  (1, 1); -  (1, 2); -  (1, 3); -  (2, 2); -  (2, 3); -  (3, 3). 
In the fifth test sample, the following sequences are beautiful: 
 -  (1, 1), (2, 3); -  (1, 2), (3, 3). 
In the third and sixth samples, there are no beautiful sequences.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a string S consisting of digits from 1 through 9.
Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:
Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

-----Constraints-----
 - 1 ≤ |S| ≤ 200000
 - S is a string consisting of digits from 1 through 9.

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

-----Output-----
Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

-----Sample Input-----
1817181712114

-----Sample Output-----
3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iahub likes chess very much. He even invented a new chess piece named Coder. A Coder can move (and attack) one square horizontally or vertically. More precisely, if the Coder is located at position (x, y), he can move to (or attack) positions (x + 1, y), (x–1, y), (x, y + 1) and (x, y–1).

Iahub wants to know how many Coders can be placed on an n × n chessboard, so that no Coder attacks any other Coder.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 1000).


-----Output-----

On the first line print an integer, the maximum number of Coders that can be placed on the chessboard.

On each of the next n lines print n characters, describing the configuration of the Coders. For an empty cell print an '.', and for a Coder print a 'C'.

If there are multiple correct answers, you can print any.


-----Examples-----
Input
2

Output
2
C.
.C

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