vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Bob watches TV every day. He always sets the volume of his TV to $b$. However, today he is angry to find out someone has changed the volume to $a$. Of course, Bob has a remote control that can change the volume.

There are six buttons ($-5, -2, -1, +1, +2, +5$) on the control, which in one press can either increase or decrease the current volume by $1$, $2$, or $5$. The volume can be arbitrarily large, but can never be negative. In other words, Bob cannot press the button if it causes the volume to be lower than $0$.

As Bob is so angry, he wants to change the volume to $b$ using as few button presses as possible. However, he forgets how to do such simple calculations, so he asks you for help. Write a program that given $a$ and $b$, finds the minimum number of presses to change the TV volume from $a$ to $b$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 1\,000$). Then the descriptions of the test cases follow.

Each test case consists of one line containing two integers $a$ and $b$ ($0 \le a, b \le 10^{9}$) — the current volume and Bob's desired volume, respectively.


-----Output-----

For each test case, output a single integer — the minimum number of presses to change the TV volume from $a$ to $b$. If Bob does not need to change the volume (i.e. $a=b$), then print $0$.


-----Example-----
Input
3
4 0
5 14
3 9

Output
2
3
2



-----Note-----

In the first example, Bob can press the $-2$ button twice to reach $0$. Note that Bob can not press $-5$ when the volume is $4$ since it will make the volume negative. 

In the second example, one of the optimal ways for Bob is to press the $+5$ twice, then press $-1$ once.

In the last example, Bob can press the $+5$ once, then press $+1$.

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

There is a war and nobody knows - the alphabet war!  
There are two groups of hostile letters. The tension between left side letters and right side letters was too high and the war began. The letters called airstrike to help them in war - dashes and dots are spreaded everywhere on the battlefield.

# Task

Write a function that accepts `fight` string consists of only small letters and `*` which means a bomb drop place. Return who wins the fight after bombs are exploded. When the left side wins return `Left side wins!`, when the right side wins return `Right side wins!`, in other case return `Let's fight again!`.

The left side letters and their power:
```
 w - 4
 p - 3 
 b - 2
 s - 1
```
The right side letters and their power:
```
 m - 4
 q - 3 
 d - 2
 z - 1
```
The other letters don't have power and are only victims.  
The `*` bombs kills the adjacent letters ( i.e. `aa*aa` => `a___a`, `**aa**` => `______` );

# Example

# Alphabet war Collection



Alphavet war 


Alphabet war - airstrike - letters massacre


Alphabet wars - reinforces massacre


Alphabet wars - nuclear strike


Alphabet war - Wo lo loooooo priests join the war

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rooted tree is a connected graph without any simple cycles with one vertex selected as a root. In this problem the vertex number 1 will always serve as a root.

Lowest common ancestor of two vertices u and v is the farthest from the root vertex that lies on both the path from u to the root and on path from v to the root. We will denote it as LCA(u, v).

Sandy had a rooted tree consisting of n vertices that she used to store her nuts. Unfortunately, the underwater storm broke her tree and she doesn't remember all it's edges. She only managed to restore m edges of the initial tree and q triples ai, bi and ci, for which she supposes LCA(ai, bi) = ci.

Help Sandy count the number of trees of size n with vertex 1 as a root, that match all the information she remembered. If she made a mess and there are no such trees then print 0. Two rooted trees are considered to be distinct if there exists an edge that occur in one of them and doesn't occur in the other one.

Input

The first line of the input contains three integers n, m and q (1 ≤ n ≤ 13, 0 ≤ m < n, 0 ≤ q ≤ 100) — the number of vertices, the number of edges and LCA triples remembered by Sandy respectively.

Each of the next m lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the numbers of vertices connected by the i-th edge. It's guaranteed that this set of edges is a subset of edges of some tree.

The last q lines contain the triplets of numbers ai, bi, ci (1 ≤ ai, bi, ci ≤ n). Each of these triples define LCA(ai, bi) = ci. It's not guaranteed that there exists a tree that satisfy all the given LCA conditions.

Output

Print a single integer — the number of trees of size n that satisfy all the conditions.

Examples

Input

4 0 0


Output

16


Input

4 0 1
3 4 2


Output

1


Input

3 1 0
1 2


Output

2


Input

3 0 2
2 3 2
2 3 1


Output

0


Input

4 1 2
1 2
2 2 2
3 4 2


Output

1

Note

In the second sample correct answer looks like this:

<image>

In the third sample there are two possible trees:

<image> <image>

In the fourth sample the answer is 0 because the information about LCA is inconsistent.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Consider a sequence [*a*1,<=*a*2,<=... ,<=*a**n*]. Define its prefix product sequence .

Now given *n*, find a permutation of [1,<=2,<=...,<=*n*], such that its prefix product sequence is a permutation of [0,<=1,<=...,<=*n*<=-<=1].

Input Specification:
The only input line contains an integer *n* (1<=≤<=*n*<=≤<=105).

Output Specification:
In the first output line, print "YES" if such sequence exists, or print "NO" if no such sequence exists.

If any solution exists, you should output *n* more lines. *i*-th line contains only an integer *a**i*. The elements of the sequence should be different positive integers no larger than *n*.

If there are multiple solutions, you are allowed to print any of them.

Demo Input:
['7\n', '6\n']

Demo Output:
['YES\n1\n4\n3\n6\n5\n2\n7\n', 'NO\n']

Note:
For the second sample, there are no valid sequences.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given the number n, return a string which shows the minimum number of moves to complete the tower of Hanoi consisting of n layers.
Tower of Hanoi : https://en.wikipedia.org/wiki/Tower_of_Hanoi

Example - 2 layered Tower of Hanoi 

Input: n=2

Start
[[2, 1], [], []]

Goal
[[], [], [2, 1]]

Expected Output : '[[2, 1], [], []]\n[[2], [1], []]\n[[], [1], [2]]\n[[], [], [2, 1]]'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer $n$. In $1$ move, you can do one of the following actions:

erase any digit of the number (it's acceptable that the number before the operation has exactly one digit and after the operation, it is "empty");

add one digit to the right.

The actions may be performed in any order any number of times.

Note that if, after deleting some digit from a number, it will contain leading zeroes, they will not be deleted. E.g. if you delete from the number $301$ the digit $3$, the result is the number $01$ (not $1$).

You need to perform the minimum number of actions to make the number any power of $2$ (i.e. there's an integer $k$ ($k \ge 0$) such that the resulting number is equal to $2^k$). The resulting number must not have leading zeroes.

E.g. consider $n=1052$. The answer is equal to $2$. First, let's add to the right one digit $4$ (the result will be $10524$). Then let's erase the digit $5$, so the result will be $1024$ which is a power of $2$.

E.g. consider $n=8888$. The answer is equal to $3$. Let's erase any of the digits $8$ three times. The result will be $8$ which is a power of $2$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of one line containing one integer $n$ ($1 \le n \le 10^9$).


-----Output-----

For each test case, output in a separate line one integer $m$ — the minimum number of moves to transform the number into any power of $2$.


-----Examples-----

Input
12
1052
8888
6
75
128
1
301
12048
1504
6656
1000000000
687194767
Output
2
3
1
3
0
0
2
1
3
4
9
2


-----Note-----

The answer for the first test case was considered above.

The answer for the second test case was considered above.

In the third test case, it's enough to add to the right the digit $4$ — the number $6$ will turn into $64$.

In the fourth test case, let's add to the right the digit $8$ and then erase $7$ and $5$ — the taken number will turn into $8$.

The numbers of the fifth and the sixth test cases are already powers of two so there's no need to make any move.

In the seventh test case, you can delete first of all the digit $3$ (the result is $01$) and then the digit $0$ (the result is $1$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.

The grid is said to be good if and only if the following condition is satisfied:

* From (1, 1), we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.



Note that (1, 1) and (H, W) must be white if the grid is good.

Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.

* Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) - that is, from white to black and vice versa.

Constraints

* 2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:


H W
s_{11} s_{12} \cdots s_{1W}
s_{21} s_{22} \cdots s_{2W}
\vdots
s_{H1} s_{H2} \cdots s_{HW}


Here s_{rc} represents the color of (r, c) - `#` stands for black, and `.` stands for white.

Output

Print the minimum number of operations needed.

Examples

Input

3 3
.##
.#.
##.


Output

1


Input

3 3
.##
.#.
.


Output

1


Input

2 2
.
.#


Output

2


Input

4 4
..##
...
.
.


Output

0


Input

5 5
.#.#.
.#.#
.#.#.
.#.#
.#.#.


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mehta is a very rich guy. He has $N$ types of coins, and each type of coin is available in an unlimited supply.  

So Mehta goes to a supermarket to buy monthly groceries. There he sees that every item has a unique price, that is, no two items have the same price.  

Now, the supermarket owner tells Mehta that they are selling items in the price range $[L,R]$ only on that particular day. He also tells Mehta that for every price, there is an item in the shop.  

The supermarket has recently adopted a weird new tradition: Mehta may only use a single type of coin for each item he purchases. For example, he could pay for an item of price 4 with two 2-coins, but not with a 3-coin and a 1-coin.  

As you know Mehta is very weak at calculations, so he wants you to do these calculations for him and tell how many different types of items he can buy.  

Input Format 

The first line of input contains $N$, the number of types of coins Mehta has. 

Then the next $N$ lines contain an integer each: the i^{th} line contains $A[i]$, the value of Mehta's i^{th} type of coin.  

Then the next line contains a number $\mbox{D}$, the number of days Mehta goes shopping. 

Then each of the next $\mbox{D}$ lines contains numbers $\boldsymbol{\mbox{L}}$ and $\mbox{R}$, denoting that they are selling items in price range $[L,R]$ on that particular day.  

Output format 

There will be $\mbox{D}$ lines, each containing the number of distinct items that can be bought at that particular day.  

Constraints 

$1\leq N\leq17$ 

$1\leq A[i]\leq51$ 

$1\leq D\leq101$ 

$1\leq L\leq R\leq10^{18}$  

Sample Input  

4
2
3
4
5
3
1 10
2 20
3 7

Sample output

8
14
4

Explanation 

For $L=1$ and $R=10$ you can buy items of price $\{2,3,4,5,6,8,9,10\}$. 

For $L=2$ and $\textbf{R}=20$ you can buy items of price $\text{{2,3,4,5,6,8,9,10,12,14,15,16,18,20}}$. 

For $L=3$ and $R=7$ you can buy items of price $\{3,4,5,6\}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ seats in the train's car and there is exactly one passenger occupying every seat. The seats are numbered from $1$ to $n$ from left to right. The trip is long, so each passenger will become hungry at some moment of time and will go to take boiled water for his noodles. The person at seat $i$ ($1 \leq i \leq n$) will decide to go for boiled water at minute $t_i$.

Tank with a boiled water is located to the left of the $1$-st seat. In case too many passengers will go for boiled water simultaneously, they will form a queue, since there can be only one passenger using the tank at each particular moment of time. Each passenger uses the tank for exactly $p$ minutes. We assume that the time it takes passengers to go from their seat to the tank is negligibly small. 

Nobody likes to stand in a queue. So when the passenger occupying the $i$-th seat wants to go for a boiled water, he will first take a look on all seats from $1$ to $i - 1$. In case at least one of those seats is empty, he assumes that those people are standing in a queue right now, so he would be better seating for the time being. However, at the very first moment he observes that all seats with numbers smaller than $i$ are busy, he will go to the tank.

There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them (that is, seating on the seat with smallest number) will go to the tank, while all others will wait for the next moment.

Your goal is to find for each passenger, when he will receive the boiled water for his noodles.


-----Input-----

The first line contains integers $n$ and $p$ ($1 \leq n \leq 100\,000$, $1 \leq p \leq 10^9$) — the number of people and the amount of time one person uses the tank.

The second line contains $n$ integers $t_1, t_2, \dots, t_n$ ($0 \leq t_i \leq 10^9$) — the moments when the corresponding passenger will go for the boiled water.


-----Output-----

Print $n$ integers, where $i$-th of them is the time moment the passenger on $i$-th seat will receive his boiled water.


-----Example-----
Input
5 314
0 310 942 628 0

Output
314 628 1256 942 1570 



-----Note-----

Consider the example.

At the $0$-th minute there were two passengers willing to go for a water, passenger $1$ and $5$, so the first passenger has gone first, and returned at the $314$-th minute. At this moment the passenger $2$ was already willing to go for the water, so the passenger $2$ has gone next, and so on. In the end, $5$-th passenger was last to receive the boiled water.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the function that takes a string as an input, and return a list of all the unpaired characters (i.e. they show up an odd number of times in the string), in the order they were encountered as an array. 

In case of multiple appearances to choose from, take the last occurence of the unpaired character.

**Notes:**
* A wide range of characters is used, and some of them may not render properly in your browser.
* Your solution should be linear in terms of string length to pass the last test.


## Examples

```
"Hello World"   -->  ["H", "e", " ", "W", "r", "l", "d"]
"Codewars"      -->  ["C", "o", "d", "e", "w", "a", "r", "s"]
"woowee"        -->  []
"wwoooowweeee"  -->  []
"racecar"       -->  ["e"]
"Mamma"         -->  ["M"]
"Mama"          -->  ["M", "m"]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Devu being a small kid, likes to play a lot, but he only likes to play with arrays. While playing he came up with an interesting question which he could not solve, can you please solve it for him?

Given an array consisting of distinct integers. Is it possible to partition the whole array into k disjoint non-empty parts such that p of the parts have even sum (each of them must have even sum) and remaining k - p have odd sum? (note that parts need not to be continuous).

If it is possible to partition the array, also give any possible way of valid partitioning.


-----Input-----

The first line will contain three space separated integers n, k, p (1 ≤ k ≤ n ≤ 10^5; 0 ≤ p ≤ k). The next line will contain n space-separated distinct integers representing the content of array a: a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

In the first line print "YES" (without the quotes) if it is possible to partition the array in the required way. Otherwise print "NO" (without the quotes).

If the required partition exists, print k lines after the first line. The i^{th} of them should contain the content of the i^{th} part. Print the content of the part in the line in the following way: firstly print the number of elements of the part, then print all the elements of the part in arbitrary order. There must be exactly p parts with even sum, each of the remaining k - p parts must have odd sum.

As there can be multiple partitions, you are allowed to print any valid partition.


-----Examples-----
Input
5 5 3
2 6 10 5 9

Output
YES
1 9
1 5
1 10
1 6
1 2

Input
5 5 3
7 14 2 9 5

Output
NO

Input
5 3 1
1 2 3 7 5

Output
YES
3 5 1 3
1 7
1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Inzane finally found Zane with a lot of money to spare, so they together decided to establish a country of their own.

Ruling a country is not an easy job. Thieves and terrorists are always ready to ruin the country's peace. To fight back, Zane and Inzane have enacted a very effective law: from each city it must be possible to reach a police station by traveling at most d kilometers along the roads. [Image] 

There are n cities in the country, numbered from 1 to n, connected only by exactly n - 1 roads. All roads are 1 kilometer long. It is initially possible to travel from a city to any other city using these roads. The country also has k police stations located in some cities. In particular, the city's structure satisfies the requirement enforced by the previously mentioned law. Also note that there can be multiple police stations in one city.

However, Zane feels like having as many as n - 1 roads is unnecessary. The country is having financial issues, so it wants to minimize the road maintenance cost by shutting down as many roads as possible.

Help Zane find the maximum number of roads that can be shut down without breaking the law. Also, help him determine such roads.


-----Input-----

The first line contains three integers n, k, and d (2 ≤ n ≤ 3·10^5, 1 ≤ k ≤ 3·10^5, 0 ≤ d ≤ n - 1) — the number of cities, the number of police stations, and the distance limitation in kilometers, respectively.

The second line contains k integers p_1, p_2, ..., p_{k} (1 ≤ p_{i} ≤ n) — each denoting the city each police station is located in.

The i-th of the following n - 1 lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the cities directly connected by the road with index i.

It is guaranteed that it is possible to travel from one city to any other city using only the roads. Also, it is possible from any city to reach a police station within d kilometers.


-----Output-----

In the first line, print one integer s that denotes the maximum number of roads that can be shut down.

In the second line, print s distinct integers, the indices of such roads, in any order.

If there are multiple answers, print any of them.


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

Output
1
5

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

Output
2
4 5 


-----Note-----

In the first sample, if you shut down road 5, all cities can still reach a police station within k = 4 kilometers.

In the second sample, although this is the only largest valid set of roads that can be shut down, you can print either 4 5 or 5 4 in the second line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Speedcubing is the hobby involving solving a variety of twisty puzzles, the most famous being the 3x3x3 puzzle or Rubik's Cube, as quickly as possible.

In the majority of Speedcubing competitions, a Cuber solves a scrambled cube 5 times, and their result is found by taking the average of the middle 3 solves (ie. the slowest and fastest times are disregarded, and an average is taken of the remaining times).

In some competitions, the unlikely event of a tie situation is resolved by comparing Cuber's fastest times.

Write a function ```cube_times(times)``` that, given an array of floats ```times``` returns an array / tuple with the Cuber's result (to 2 decimal places) AND their fastest solve.

For example:
```python
cube_times([9.5, 7.6, 11.4, 10.5, 8.1]) = (9.37, 7.6)
# Because (9.5 + 10.5 + 8.1) / 3 = 9.37 and 7.6 was the fastest solve.
```

Note: ```times``` will always be a valid array of 5 positive floats (representing seconds)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
PolandBall is a young, clever Ball. He is interested in prime numbers. He has stated a following hypothesis: "There exists such a positive integer n that for each positive integer m number n·m + 1 is a prime number".

Unfortunately, PolandBall is not experienced yet and doesn't know that his hypothesis is incorrect. Could you prove it wrong? Write a program that finds a counterexample for any n.


-----Input-----

The only number in the input is n (1 ≤ n ≤ 1000) — number from the PolandBall's hypothesis. 


-----Output-----

Output such m that n·m + 1 is not a prime number. Your answer will be considered correct if you output any suitable m such that 1 ≤ m ≤ 10^3. It is guaranteed the the answer exists.


-----Examples-----
Input
3

Output
1
Input
4

Output
2


-----Note-----

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

For the first sample testcase, 3·1 + 1 = 4. We can output 1.

In the second sample testcase, 4·1 + 1 = 5. We cannot output 1 because 5 is prime. However, m = 2 is okay since 4·2 + 1 = 9, which is not a prime number.

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