vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
=====Function Descriptions=====
If we want to add a single element to an existing set, we can use the .add() operation.
It adds the element to the set and returns 'None'.

=====Example=====
>>> s = set('HackerRank')
>>> s.add('H')
>>> print s
set(['a', 'c', 'e', 'H', 'k', 'n', 'r', 'R'])
>>> print s.add('HackerRank')
None
>>> print s
set(['a', 'c', 'e', 'HackerRank', 'H', 'k', 'n', 'r', 'R'])

=====Problem Statement=====
Apply your knowledge of the .add() operation to help your friend Rupal.
Rupal has a huge collection of country stamps. She decided to count the total number of distinct country stamps in her collection. She asked for your help. You pick the stamps one by one from a stack of N country stamps.
Find the total number of distinct country stamps.

=====Input Format=====
The fist line contains an integer N, the total number of country stamps.
The next N lines contains the name of the country where the stamp is from.

=====Constraints=====
0<N<1000

=====Output Format=====
Output the total number of distinct country stamps on a single line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i.
Consider painting each of these edges white or black. There are 2^{N-1} such ways to paint the edges. Among them, how many satisfy all of the following M restrictions?

* The i-th (1 \leq i \leq M) restriction is represented by two integers u_i and v_i, which mean that the path connecting Vertex u_i and Vertex v_i must contain at least one edge painted black.

Constraints

* 2 \leq N \leq 50
* 1 \leq a_i,b_i \leq N
* The graph given in input is a tree.
* 1 \leq M \leq \min(20,\frac{N(N-1)}{2})
* 1 \leq u_i < v_i \leq N
* If i \not= j, either u_i \not=u_j or v_i\not=v_j
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
M
u_1 v_1
:
u_M v_M


Output

Print the number of ways to paint the edges that satisfy all of the M conditions.

Examples

Input

3
1 2
2 3
1
1 3


Output

3


Input

2
1 2
1
1 2


Output

1


Input

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


Output

9


Input

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


Output

62

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima took up the biology of bacteria, as a result of his experiments, he invented k types of bacteria. Overall, there are n bacteria at his laboratory right now, and the number of bacteria of type i equals ci. For convenience, we will assume that all the bacteria are numbered from 1 to n. The bacteria of type ci are numbered from <image> to <image>.

With the help of special equipment Dima can move energy from some bacteria into some other one. Of course, the use of such equipment is not free. Dima knows m ways to move energy from some bacteria to another one. The way with number i can be described with integers ui, vi and xi mean that this way allows moving energy from bacteria with number ui to bacteria with number vi or vice versa for xi dollars.

Dima's Chef (Inna) calls the type-distribution correct if there is a way (may be non-direct) to move energy from any bacteria of the particular type to any other bacteria of the same type (between any two bacteria of the same type) for zero cost.

As for correct type-distribution the cost of moving the energy depends only on the types of bacteria help Inna to determine is the type-distribution correct? If it is, print the matrix d with size k × k. Cell d[i][j] of this matrix must be equal to the minimal possible cost of energy-moving from bacteria with type i to bacteria with type j.

Input

The first line contains three integers n, m, k (1 ≤ n ≤ 105; 0 ≤ m ≤ 105; 1 ≤ k ≤ 500). The next line contains k integers c1, c2, ..., ck (1 ≤ ci ≤ n). Each of the next m lines contains three integers ui, vi, xi (1 ≤ ui, vi ≤ 105; 0 ≤ xi ≤ 104). It is guaranteed that <image>.

Output

If Dima's type-distribution is correct, print string «Yes», and then k lines: in the i-th line print integers d[i][1], d[i][2], ..., d[i][k] (d[i][i] = 0). If there is no way to move energy from bacteria i to bacteria j appropriate d[i][j] must equal to -1. If the type-distribution isn't correct print «No».

Examples

Input

4 4 2
1 3
2 3 0
3 4 0
2 4 1
2 1 2


Output

Yes
0 2
2 0


Input

3 1 2
2 1
1 2 0


Output

Yes
0 -1
-1 0


Input

3 2 2
2 1
1 2 0
2 3 1


Output

Yes
0 1
1 0


Input

3 0 2
1 2


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer $n$, written without leading zeroes (for example, the number 04 is incorrect). 

In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros.

Determine the minimum number of operations that you need to consistently apply to the given integer $n$ to make from it the square of some positive integer or report that it is impossible.

An integer $x$ is the square of some positive integer if and only if $x=y^2$ for some positive integer $y$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{9}$). The number is given without leading zeroes.


-----Output-----

If it is impossible to make the square of some positive integer from $n$, print -1. In the other case, print the minimal number of operations required to do it.


-----Examples-----
Input
8314

Output
2

Input
625

Output
0

Input
333

Output
-1



-----Note-----

In the first example we should delete from $8314$ the digits $3$ and $4$. After that $8314$ become equals to $81$, which is the square of the integer $9$.

In the second example the given $625$ is the square of the integer $25$, so you should not delete anything. 

In the third example it is impossible to make the square from $333$, so the answer is -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem.

This is a hard version of the problem. The difference from the easy version is that in the hard version 1 ≤ t ≤ min(n, 10^4) and the total number of queries is limited to 6 ⋅ 10^4.

Polycarp is playing a computer game. In this game, an array consisting of zeros and ones is hidden. Polycarp wins if he guesses the position of the k-th zero from the left t times.

Polycarp can make no more than 6 ⋅ 10^4 requests totally of the following type: 

  * ? l r — find out the sum of all elements in positions from l to r (1 ≤ l ≤ r ≤ n) inclusive. 



To make the game more interesting, each guessed zero turns into one and the game continues on the changed array. More formally, if the position of the k-th zero was x, then after Polycarp guesses this position, the x-th element of the array will be replaced from 0 to 1.

Help Polycarp win the game.

Interaction

First, your program must read two integers n and t (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ t ≤ min(n, 10^4)).

Then t lines follow, each of which contains one integer k (1 ≤ k ≤ n). It is guaranteed that at the moment of the request the array contains at least k zeros. In order to get the next value of k, you must output the answer for the previous value of k.

After that, you can make no more than 6 ⋅ 10^4 requests in total.

Use the following format to output the answer (it is not a request, it doesn't count in 6 ⋅ 10^4): 

  * ! x — position of the k-th zero. 



Positions in the array are numbered from left to right from 1 to n inclusive.

After printing t answers, your program should exit immediately.

In this task, the interactor is not adaptive. This means that within the same test, the hidden array and the queries do not change.

In case of an incorrect query, -1 will be displayed. When this value is received, your program must immediately exit normally (for example, by calling exit(0)), otherwise, the testing system may issue an arbitrary verdict.

If the number of requests is exceeded, the verdict wrong answer will be displayed.

Your solution may get the verdict Idleness limit exceeded if you don't print anything or forget to flush the output buffer.

To flush the output buffer, you need to do the following immediately after the query output and the end-of-line character:

  * fflush(stdout) or cout.flush() in C ++; 
  * System.out.flush() in Java; 
  * flush(output) in Pascal; 
  * stdout.flush() in Python; 
  * see the documentation for other languages. 



Hacks

Use the following format for hacks:

On the first line print the string s (1 ≤ |s| ≤ 2 ⋅ 10^5), consisting of zeros and ones, and an integer t (1 ≤ t ≤ min(|s|, 10^4)) — hidden array and number of requests, respectively. In the next t lines output the number k (1 ≤ k ≤ |s|).

The hacked solution will not have direct access to the hidden array.

Example

Input


6 2

2

2

1

1

0

1

0

Output


? 4 6

? 1 1

? 1 2

? 5 5

! 5

? 2 2

! 2

Note

In the first test, the array [1, 0, 1, 1, 0, 1] is hidden. After answering the query k=2, the array changed to [1, 0, 1, 1, 1, 1].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected connected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is traversed more than once, then it is included in bitwise xor the same number of times). 

There are three types of queries you have to process:

  * 1 x y d — add an edge connecting vertex x to vertex y with weight d. It is guaranteed that there is no edge connecting x to y before this query; 
  * 2 x y — remove an edge connecting vertex x to vertex y. It is guaranteed that there was such edge in the graph, and the graph stays connected after this query; 
  * 3 x y — calculate the length of the shortest path (possibly non-simple) from vertex x to vertex y. 



Print the answers for all queries of type 3.

Input

The first line contains two numbers n and m (1 ≤ n, m ≤ 200000) — the number of vertices and the number of edges in the graph, respectively.

Then m lines follow denoting the edges of the graph. Each line contains three integers x, y and d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 230 - 1). Each pair (x, y) is listed at most once. The initial graph is connected.

Then one line follows, containing an integer q (1 ≤ q ≤ 200000) — the number of queries you have to process.

Then q lines follow, denoting queries in the following form:

  * 1 x y d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 230 - 1) — add an edge connecting vertex x to vertex y with weight d. It is guaranteed that there is no edge connecting x to y before this query; 
  * 2 x y (1 ≤ x < y ≤ n) — remove an edge connecting vertex x to vertex y. It is guaranteed that there was such edge in the graph, and the graph stays connected after this query; 
  * 3 x y (1 ≤ x < y ≤ n) — calculate the length of the shortest path (possibly non-simple) from vertex x to vertex y. 



It is guaranteed that at least one query has type 3.

Output

Print the answers for all queries of type 3 in the order they appear in input.

Example

Input

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


Output

1
1
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our hero - Maga has been working on a research related to Pascal’s Triangle for about a month. He has recently found a new problematic thing for his research. He has to calculate a big number. But he is very busy. Could you do it for him?

You are given a binomial as this: (a * x + b * y)^n. You have to find the binomial coefficient of x^k * y^(n-k) modulo 10^9+7.

Input:

You are given 4 integers: each space separated integers a, b, n and k.

Output:

Output 1 integer: the binomial coefficient of x^k * y^(n-k) mod (10^9+7).

Constraints:

1 ≤ a, b ≤ 100

1 ≤ n ≤ 10^6

1 ≤ k ≤ min(n,10^5)

SAMPLE INPUT
1 1 4 2

SAMPLE OUTPUT
6

Explanation

The result is 6. In the (x+y)^4 binomial, the coefficient of x^2 * y^2 is 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iskander the Baker is decorating a huge cake, covering the rectangular surface of the cake with frosting. For this purpose, he mixes frosting sugar with lemon juice and food coloring, in order to produce three kinds of frosting: yellow, pink, and white. These colors are identified by the numbers $0$ for yellow, $1$ for pink, and $2$ for white.

To obtain a nice pattern, he partitions the cake surface into vertical stripes of width $A_1, A_2, \dots , A_ n$ centimeters, and horizontal stripes of height $B_1, B_2, \dots , B_ n$ centimeters, for some positive integer $n$. These stripes split the cake surface into $n\times n$ rectangles. The intersection of vertical stripe $i$ and horizontal stripe $j$ has color number $(i+j) \bmod 3$ for all $1 \leq i,j \leq n$. To prepare the frosting, Iskander wants to know the total surface in square centimeters to be colored for each of the three colors, and asks for your help.Input

The input consists of the following integers:
 - on the first line: the integer $n$,
 - on the second line: the values of $A_1,\dots ,A_ n$, $n$ integers separated with single spaces,
 - on the third line: the values of $B_1,\dots ,B_ n$, $n$ integers separated with single spaces.Limits

The input satisfies $3\leq n \leq 100000$ and $1 \leq A_1,\ldots ,A_ n,B_1,\ldots ,B_ n \leq 10000$.Output

The output should consist of three integers separated with single spaces, representing the total area for each color $0$, $1$, and $2$.

-----Examples-----
Sample Input:
3
1 1 1
1 1 1
Sample Output:
3 3 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program, which takes an integer N and if the number is less than 10 then display "Thanks for helping Chef!" otherwise print "-1".

-----Input-----

The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer N. 

-----Output-----
For each test case, output the given string or -1 depending on conditions, in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- -20 ≤ N ≤ 20

-----Example-----
Input
3 
1
12
-5
Output
Thanks for helping Chef!
-1
Thanks for helping Chef!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When dealt cards in the card game Plump it is a good idea to start by sorting the cards in hand by suit and rank. The different suits should be grouped and the ranks should be sorted within each suit. But the order of the suits does not matter and within each suit, the cards may be sorted in either ascending or descending order on rank. It is allowed for some suits to be sorted in ascending order and others in descending order. 

Sorting is done by moving one card at a time from its current position to a new position in the hand, at the start, end, or in between two adjacent cards. What is the smallest number of moves required to sort a given hand of cards?

-----Input-----
The first line of input contains an integer $n$ ($1 \le n \le 52$), the number of cards in the hand. The second line contains $n$ pairwise distinct space-separated cards, each represented by two characters. The first character of a card represents the rank and is either a digit from 2 to 9 or one of the letters T, J, Q, K, and A representing Ten, Jack, Queen, King and Ace, respectively, given here in increasing order. The second character of a card is from the set {s, h, d, c} representing the suits spades $\spadesuit $, hearts $\heartsuit $, diamonds $\diamondsuit $, and clubs $\clubsuit $.

-----Output-----
Output the minimum number of card moves required to sort the hand as described above.

-----Examples-----
Sample Input 1:
4
2h Th 8c Qh
Sample Output 1:
1

Sample Input 2:
7
9d As 2s Qd 2c Jd 8h
Sample Output 2:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya has a simple graph (that is, a graph without loops or multiple edges) consisting of $n$ vertices and $m$ edges.

The weight of the $i$-th vertex is $a_i$.

The weight of the $i$-th edge is $w_i$.

A subgraph of a graph is some set of the graph vertices and some set of the graph edges. The set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices. 

The weight of a subgraph is the sum of the weights of its edges, minus the sum of the weights of its vertices. You need to find the maximum weight of subgraph of given graph. The given graph does not contain loops and multiple edges.


-----Input-----

The first line contains two numbers $n$ and $m$ ($1 \le n \le 10^3, 0 \le m \le 10^3$) - the number of vertices and edges in the graph, respectively.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) - the weights of the vertices of the graph.

The following $m$ lines contain edges: the $i$-e edge is defined by a triple of integers $v_i, u_i, w_i$ ($1 \le v_i, u_i \le n, 1 \le w_i \le 10^9, v_i \neq u_i$). This triple means that between the vertices $v_i$ and $u_i$ there is an edge of weight $w_i$. It is guaranteed that the graph does not contain loops and multiple edges.


-----Output-----

Print one integer — the maximum weight of the subgraph of the given graph.


-----Examples-----
Input
4 5
1 5 2 2
1 3 4
1 4 4
3 4 5
3 2 2
4 2 2

Output
8

Input
3 3
9 7 8
1 2 1
2 3 2
1 3 3

Output
0



-----Note-----

In the first test example, the optimal subgraph consists of the vertices ${1, 3, 4}$ and has weight $4 + 4 + 5 - (1 + 2 + 2) = 8$. In the second test case, the optimal subgraph is empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment.

You are given a tree with $N$ nodes and each node's value $val_i$ is initially $0$.

Let's denote the path from node $\mbox{u}$ to node $\boldsymbol{\nu}$ like this: $p_1,p_2,p_3,\ldots,p_k$, where $p_1=u$ and $p_k=v$, and $p_i$ and $\textbf{p}_{i+1}$ are connected.  

The problem asks you to operate the following two types of queries on the tree:

"1 u v x" Add $\boldsymbol{x}$ to $val_{p_1}$, $2x$ to $val_{p_2}$, $3x$ to $val_{p_3}$, ...,  $kx$ to $val_{p_k}$. 
"2 u v" print the sum of the nodes' values on the path between $\mbox{u}$ and $\boldsymbol{\nu}$ at modulo $10^9+7$.

Input Format

First line cosists of two integers $N$ and $Q$ seperated by a space.

Following $N-1$ lines contains two integers which denote the undirectional edges of the tree.

Following $Q$ lines contains one of the query types described above.

Note: Nodes are numbered by using 0-based indexing. 

Constraints

$1\le N,Q\le50000$

$0\leq x<10^9+7$

Output Format

For every query of second type print a single integer.

Sample Input
3 2
0 1
1 2
1 0 2 1
2 1 2

Sample Output
5

Explanation

After the first type of query, $val_0=1,val_1=2,val_2=3$. Hence the answer of the second query is $2+3=5$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mike has a string *s* consisting of only lowercase English letters. He wants to change exactly one character from the string so that the resulting one is a palindrome. 

A palindrome is a string that reads the same backward as forward, for example strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

Input Specification:
The first and single line contains string *s* (1<=≤<=|*s*|<=≤<=15).

Output Specification:
Print "YES" (without quotes) if Mike can change exactly one character so that the resulting string is palindrome or "NO" (without quotes) otherwise.

Demo Input:
['abccaa\n', 'abbcca\n', 'abcda\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states:

Every even integer greater than 2 can be expressed as the sum of two primes.
For example: 

`6 = 3 + 3`
`8 = 3 + 5`
`10 = 3 + 7 = 5 + 5`
`12 = 5 + 7`

Some rules for the conjecture: 

- pairs should be descending like [3,5] not [5,3]

- all pairs should be in ascending order based on the first element of the pair: 
`[[5, 13], [7, 11]]` is accepted 
but `[[7, 11],[5, 13]]` is not accepted.

Write the a function that find all identical pairs of prime numbers:
```python
def goldbach(even_number)
```
You should return an array of containing pairs of primes, like:
```python
[[5, 13], [7, 11]]  # even_number = 18
```
or
```python
[[3, 31], [5, 29], [11, 23], [17, 17]] # even_number = 34
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everyone Knows AdFly and their Sister Sites.

If we see the Page Source of an ad.fly site we can see this perticular line:
Believe it or not This is actually the Encoded url which you would skip to.

The Algorithm is as Follows:
```
1) The ysmm value is broken like this

ysmm   = 0 1 2 3 4 5 6 7 8 9  = "0123456789"
code1  = 0   2   4   6   8    = "02468"
code2  =   9   7   5   3   1  = "97531"

2) code1+code2 is base64 Decoded

3) The result will be of this form :
https://adf.ly/go.php?u=

4)  has to be further decoded and the result is to be returned
```

Your Task:

```
Make a function to Encode text to ysmm value.

and a function to Decode ysmm value.
```

Note: Take random values for The first 2 int values.
I personally hate trivial error checking like giving integer input in place of string. 

```
Input For Decoder & Encoder: Strings
Return "Invalid" for invalid Strings
```

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