vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a grid of size n*m (n is the number of rows and m is the number of columns in the grid) consisting of '0's (Water) and '1's(Land). Find the number of islands.
Note: An island is either surrounded by water or boundary of grid and is formed by connecting adjacent lands horizontally or vertically or diagonally i.e., in all 8 directions.
Example 1:
Input:
grid = {{0,1},{1,0},{1,1},{1,0}}
Output:
1
Explanation:
The grid is-
0 1
1 0
1 1
1 0
All lands are connected.
Example 2:
Input:
grid = {{0,1,1,1,0,0,0},{0,0,1,1,0,1,0}}
Output:
2
Expanation:
The grid is-
0 1 1 1 0 0 0
0 0 1 1 0 1 0 
There are two islands :- one is colored in blue 
and other in orange.
Your Task:
You don't need to read or print anything. Your task is to complete the function numIslands() which takes the grid as an input parameter and returns the total number of islands.
Expected Time Complexity: O(n*m)
Expected Space Complexity: O(n*m)
Constraints:
1 ≤ n, m ≤ 500

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For his computer science class, Jacob builds a model tree with sticks and balls containing n nodes in the shape of a tree. Jacob has spent a_{i} minutes building the i-th ball in the tree.

Jacob's teacher will evaluate his model and grade Jacob based on the effort he has put in. However, she does not have enough time to search his whole tree to determine this; Jacob knows that she will examine the first k nodes in a DFS-order traversal of the tree. She will then assign Jacob a grade equal to the minimum a_{i} she finds among those k nodes.

Though Jacob does not have enough time to rebuild his model, he can choose the root node that his teacher starts from. Furthermore, he can rearrange the list of neighbors of each node in any order he likes. Help Jacob find the best grade he can get on this assignment.

A DFS-order traversal is an ordering of the nodes of a rooted tree, built by a recursive DFS-procedure initially called on the root of the tree. When called on a given node v, the procedure does the following:   Print v.  Traverse the list of neighbors of the node v in order and iteratively call DFS-procedure on each one. Do not call DFS-procedure on node u if you came to node v directly from u. 


-----Input-----

The first line of the input contains two positive integers, n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ n) — the number of balls in Jacob's tree and the number of balls the teacher will inspect.

The second line contains n integers, a_{i} (1 ≤ a_{i} ≤ 1 000 000), the time Jacob used to build the i-th ball.

Each of the next n - 1 lines contains two integers u_{i}, v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) representing a connection in Jacob's tree between balls u_{i} and v_{i}.


-----Output-----

Print a single integer — the maximum grade Jacob can get by picking the right root of the tree and rearranging the list of neighbors.


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

Output
3

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

Output
1



-----Note-----

In the first sample, Jacob can root the tree at node 2 and order 2's neighbors in the order 4, 1, 5 (all other nodes have at most two neighbors). The resulting preorder traversal is 2, 4, 1, 3, 5, and the minimum a_{i} of the first 3 nodes is 3.

In the second sample, it is clear that any preorder traversal will contain node 1 as either its first or second node, so Jacob cannot do better than a grade of 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two circles. Find the area of their intersection.

Input

The first line contains three integers x1, y1, r1 ( - 109 ≤ x1, y1 ≤ 109, 1 ≤ r1 ≤ 109) — the position of the center and the radius of the first circle.

The second line contains three integers x2, y2, r2 ( - 109 ≤ x2, y2 ≤ 109, 1 ≤ r2 ≤ 109) — the position of the center and the radius of the second circle.

Output

Print the area of the intersection of the circles. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

Examples

Input

0 0 4
6 0 4


Output

7.25298806364175601379


Input

0 0 5
11 0 5


Output

0.00000000000000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sometimes Mister B has free evenings when he doesn't know what to do. Fortunately, Mister B found a new game, where the player can play against aliens.

All characters in this game are lowercase English letters. There are two players: Mister B and his competitor.

Initially the players have a string s consisting of the first a English letters in alphabetical order (for example, if a = 5, then s equals to "abcde").

The players take turns appending letters to string s. Mister B moves first.

Mister B must append exactly b letters on each his move. He can arbitrary choose these letters. His opponent adds exactly a letters on each move.

Mister B quickly understood that his opponent was just a computer that used a simple algorithm. The computer on each turn considers the suffix of string s of length a and generates a string t of length a such that all letters in the string t are distinct and don't appear in the considered suffix. From multiple variants of t lexicographically minimal is chosen (if a = 4 and the suffix is "bfdd", the computer chooses string t equal to "aceg"). After that the chosen string t is appended to the end of s.

Mister B soon found the game boring and came up with the following question: what can be the minimum possible number of different letters in string s on the segment between positions l and r, inclusive. Letters of string s are numerated starting from 1.


-----Input-----

First and only line contains four space-separated integers: a, b, l and r (1 ≤ a, b ≤ 12, 1 ≤ l ≤ r ≤ 10^9) — the numbers of letters each player appends and the bounds of the segment.


-----Output-----

Print one integer — the minimum possible number of different letters in the segment from position l to position r, inclusive, in string s.


-----Examples-----
Input
1 1 1 8

Output
2
Input
4 2 2 6

Output
3
Input
3 7 4 6

Output
1


-----Note-----

In the first sample test one of optimal strategies generate string s = "abababab...", that's why answer is 2.

In the second sample test string s = "abcdbcaefg..." can be obtained, chosen segment will look like "bcdbc", that's why answer is 3.

In the third sample test string s = "abczzzacad..." can be obtained, chosen, segment will look like "zzz", that's why answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jamie is preparing a Codeforces round. He has got an idea for a problem, but does not know how to solve it. Help him write a solution to the following problem:

Find k integers such that the sum of two to the power of each number equals to the number n and the largest integer in the answer is as small as possible. As there may be multiple answers, you are asked to output the lexicographically largest one. 

To be more clear, consider all integer sequence with length k (a_1, a_2, ..., a_{k}) with $\sum_{i = 1}^{k} 2^{a_{i}} = n$. Give a value $y = \operatorname{max}_{1 \leq i \leq k} a_{i}$ to each sequence. Among all sequence(s) that have the minimum y value, output the one that is the lexicographically largest.

For definitions of powers and lexicographical order see notes.


-----Input-----

The first line consists of two integers n and k (1 ≤ n ≤ 10^18, 1 ≤ k ≤ 10^5) — the required sum and the length of the sequence.


-----Output-----

Output "No" (without quotes) in a single line if there does not exist such sequence. Otherwise, output "Yes" (without quotes) in the first line, and k numbers separated by space in the second line — the required sequence.

It is guaranteed that the integers in the answer sequence fit the range [ - 10^18, 10^18].


-----Examples-----
Input
23 5

Output
Yes
3 3 2 1 0 

Input
13 2

Output
No

Input
1 2

Output
Yes
-1 -1 



-----Note-----

Sample 1:

2^3 + 2^3 + 2^2 + 2^1 + 2^0 = 8 + 8 + 4 + 2 + 1 = 23

Answers like (3, 3, 2, 0, 1) or (0, 1, 2, 3, 3) are not lexicographically largest.

Answers like (4, 1, 1, 1, 0) do not have the minimum y value.

Sample 2:

It can be shown there does not exist a sequence with length 2.

Sample 3:

$2^{-1} + 2^{-1} = \frac{1}{2} + \frac{1}{2} = 1$

Powers of 2:

If x > 0, then 2^{x} = 2·2·2·...·2 (x times).

If x = 0, then 2^{x} = 1.

If x < 0, then $2^{x} = \frac{1}{2^{-x}}$.

Lexicographical order:

Given two different sequences of the same length, (a_1, a_2, ... , a_{k}) and (b_1, b_2, ... , b_{k}), the first one is smaller than the second one for the lexicographical order, if and only if a_{i} < b_{i}, for the first i where a_{i} and b_{i} differ.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A brokerage firm is interested in detecting automatic trading. They believe that a particular algorithm repeats itself; that is, it makes the same sequence of trades at a later time. The firm has identified a set of 26 key stocks that they believe are likely to be traded in concert, and they’ve encoded a series of trades as a string of letters: the letter itself indicates the stock, upper case indicates a buy, lower case indicates a sell. They want you to write a program to determine, for any two starting points, the longest sequence of identical trades from those two starting points, starting from and including those starting points as the first trade in the sequence.

-----Input-----
There will be a single test case in the input. This test case will start with a string $s$ on the first line, consisting solely of upper case and lower case letters ($1 \le \text {length}(s) \le 100000$). On the next line will be an integer $q$ ($1 \le q \le 100000$), indicating the number of queries. The following $q$ lines each describe a query with two integers, $i$ and $j$ ($0 \le i < j < \text {length}(s)$), which represent two zero-based positions in the string.

-----Output-----
For each query, output a single integer, indicating the length of the longest sequence of trades starting at $i$ which is identical to the sequence of trades starting at $j$.

-----Examples-----
Sample Input:
ABABABcABABAbAbab
3
0 2
1 6
0 7
Sample Output:
4
0
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our good friend Mole is trying to code a big message. He is typing on an unusual keyboard with characters arranged in following way:

qwertyuiop

asdfghjkl;

zxcvbnm,./



Unfortunately Mole is blind, so sometimes it is problem for him to put his hands accurately. He accidentally moved both his hands with one position to the left or to the right. That means that now he presses not a button he wants, but one neighboring button (left or right, as specified in input).

We have a sequence of characters he has typed and we want to find the original message.


-----Input-----

First line of the input contains one letter describing direction of shifting ('L' or 'R' respectively for left or right).

Second line contains a sequence of characters written by Mole. The size of this sequence will be no more than 100. Sequence contains only symbols that appear on Mole's keyboard. It doesn't contain spaces as there is no space on Mole's keyboard.

It is guaranteed that even though Mole hands are moved, he is still pressing buttons on keyboard and not hitting outside it.


-----Output-----

Print a line that contains the original message.


-----Examples-----
Input
R
s;;upimrrfod;pbr

Output
allyouneedislove

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the year 2420 humans have finally built a colony on Mars thanks to the work of Elon Tusk. There are 10^9+7 cities arranged in a circle in this colony and none of them are connected yet. Elon Tusk wants to connect some of those cities using only roads of the same size in order to lower the production cost of those roads. Because of that he gave a list on N cites where some cites can appear more than once and Q queries that you need to answer. For the query you need to determine if it is possible to connect all the cities from L_{i} to R_{i} on that list using only roads of length D_{i}. 

Input

The first line contains two integers N and Q (1 ≤ N, Q ≤ 2⋅10^5 ) — the length of the array of cities and the number of queries you need to answer. 

The second lines contains N integers representing the array of cites. Next Q lines contain three integers L, R and D (1 ≤ L_{i}, R_{i} ≤ N, 0 ≤ D_{i} ≤ 10^9+6) — the range of cities that needs to be connected and the length of the road that you can use. 

Output

The output contains Q lines. If it is possible to connect all the cities from the i-th query can be connected with roads of length D_{i} the i-th line should contain the word "Yes", otherwise it should contain the word "No". 

Examples

Input


9 8
17 0 12 6 10 8 2 4 5
2 3 12
2 3 6
2 4 6
4 6 2
2 8 2
1 2 17
1 8 2
9 9 14


Output


Yes
No
Yes
Yes
Yes
Yes
No
Yes


Input


4 1
7 21 14 0
1 4 1000000000


Output


Yes

Note

In the 5^{th} query of the first test case we can connect cities in this order 0-2-4-6-8-10-12 this way distance between any two connected cities is 2. In the second test case we can connect cities in this order 21-14-7-0 this way distance between any two connected cities is 10^9 module 10^9+7.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The input contains a single integer *a* (1<=≤<=*a*<=≤<=30).

Output a single integer.

Input Specification:
The input contains a single integer *a* (1<=≤<=*a*<=≤<=30).

Output Specification:
Output a single integer.

Demo Input:
['3\n']

Demo Output:
['27\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two tables A and B of size n × m. 

We define a sorting by column as the following: we choose a column and reorder the rows of the table by the value in this column, from the rows with the smallest value to the rows with the largest. In case there are two or more rows with equal value in this column, their relative order does not change (such sorting algorithms are called stable).

You can find this behavior of sorting by column in many office software for managing spreadsheets. Petya works in one, and he has a table A opened right now. He wants to perform zero of more sortings by column to transform this table to table B.

Determine if it is possible to do so, and if yes, find a sequence of columns to sort by. Note that you do not need to minimize the number of sortings.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 1500) — the sizes of the tables.

Each of the next n lines contains m integers a_{i,j} (1 ≤ a_{i, j} ≤ n), denoting the elements of the table A.

Each of the next n lines contains m integers b_{i, j} (1 ≤ b_{i, j} ≤ n), denoting the elements of the table B.

Output

If it is not possible to transform A into B, print -1.

Otherwise, first print an integer k (0 ≤ k ≤ 5000) — the number of sortings in your solution.

Then print k integers c_1, …, c_k (1 ≤ c_i ≤ m) — the columns, by which Petya needs to perform a sorting.

We can show that if a solution exists, there is one in no more than 5000 sortings.

Examples

Input


2 2
2 2
1 2
1 2
2 2


Output


1
1

Input


3 3
2 3 2
1 3 3
1 1 2
1 1 2
1 3 3
2 3 2


Output


2
1 2

Input


2 2
1 1
2 1
2 1
1 1


Output


-1

Input


4 1
2
2
2
1
1
2
2
2


Output


1
1 

Note

Consider the second example. After the sorting by the first column the table becomes

$$$\begin{matrix} 1&3&3\\\ 1&1&2\\\ 2&3&2. \end{matrix}$$$

After the sorting by the second column the table becomes

$$$\begin{matrix} 1&1&2\\\ 1&3&3\\\ 2&3&2, \end{matrix}$$$

and this is what we need.

In the third test any sorting does not change anything, because the columns are already sorted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A way to make a new task is to make it nondeterministic or probabilistic. For example, the hard task of Topcoder SRM 595, Constellation, is the probabilistic version of a convex hull.

Let's try to make a new task. Firstly we will use the following task. There are n people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are n people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation p?

More formally, if we denote the handle of the i-th person as h_{i}, then the following condition must hold: $\forall i, j(i < j) : h_{p_{i}} < h_{p_{j}}$.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of people.

The next n lines each contains two strings. The i-th line contains strings f_{i} and s_{i} (1 ≤ |f_{i}|, |s_{i}| ≤ 50) — the first name and last name of the i-th person. Each string consists only of lowercase English letters. All of the given 2n strings will be distinct.

The next line contains n distinct integers: p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n).


-----Output-----

If it is possible, output "YES", otherwise output "NO".


-----Examples-----
Input
3
gennady korotkevich
petr mitrichev
gaoyuan chen
1 2 3

Output
NO

Input
3
gennady korotkevich
petr mitrichev
gaoyuan chen
3 1 2

Output
YES

Input
2
galileo galilei
nicolaus copernicus
2 1

Output
YES

Input
10
rean schwarzer
fei claussell
alisa reinford
eliot craig
laura arseid
jusis albarea
machias regnitz
sara valestin
emma millstein
gaius worzel
1 2 3 4 5 6 7 8 9 10

Output
NO

Input
10
rean schwarzer
fei claussell
alisa reinford
eliot craig
laura arseid
jusis albarea
machias regnitz
sara valestin
emma millstein
gaius worzel
2 4 9 6 5 7 1 3 8 10

Output
YES



-----Note-----

In example 1 and 2, we have 3 people: tourist, Petr and me (cgy4ever). You can see that whatever handle is chosen, I must be the first, then tourist and Petr must be the last.

In example 3, if Copernicus uses "copernicus" as his handle, everything will be alright.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maxim has opened his own restaurant! The restaurant has got a huge table, the table's length is p meters.

Maxim has got a dinner party tonight, n guests will come to him. Let's index the guests of Maxim's restaurant from 1 to n. Maxim knows the sizes of all guests that are going to come to him. The i-th guest's size (ai) represents the number of meters the guest is going to take up if he sits at the restaurant table.

Long before the dinner, the guests line up in a queue in front of the restaurant in some order. Then Maxim lets the guests in, one by one. Maxim stops letting the guests in when there is no place at the restaurant table for another guest in the queue. There is no place at the restaurant table for another guest in the queue, if the sum of sizes of all guests in the restaurant plus the size of this guest from the queue is larger than p. In this case, not to offend the guest who has no place at the table, Maxim doesn't let any other guest in the restaurant, even if one of the following guests in the queue would have fit in at the table.

Maxim is now wondering, what is the average number of visitors who have come to the restaurant for all possible n! orders of guests in the queue. Help Maxim, calculate this number.

Input

The first line contains integer n (1 ≤ n ≤ 50) — the number of guests in the restaurant. The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 50) — the guests' sizes in meters. The third line contains integer p (1 ≤ p ≤ 50) — the table's length in meters. 

The numbers in the lines are separated by single spaces.

Output

In a single line print a real number — the answer to the problem. The answer will be considered correct, if the absolute or relative error doesn't exceed 10 - 4.

Examples

Input

3
1 2 3
3


Output

1.3333333333

Note

In the first sample the people will come in the following orders: 

  * (1, 2, 3) — there will be two people in the restaurant; 
  * (1, 3, 2) — there will be one person in the restaurant; 
  * (2, 1, 3) — there will be two people in the restaurant; 
  * (2, 3, 1) — there will be one person in the restaurant; 
  * (3, 1, 2) — there will be one person in the restaurant; 
  * (3, 2, 1) — there will be one person in the restaurant. 



In total we get (2 + 1 + 2 + 1 + 1 + 1) / 6 = 8 / 6 = 1.(3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are hired as a level designer for the next Pokémon series, with games called Ice and Fire. For the first of these two games, players have to get through a maze in an icy cave. The cave is represented as a grid, with each square of the grid being either ice, gravel or an obstacle.

The player will start at a square, and then make a number of moves, each move represented by one of the four cardinal directions. The maze behaves in the following way. Assume that the square the player is trying to move into is an obstacle. In this case, the player does not move. If the square the player is moving into is gravel, the player successfully moves to the square and will stand still on the square. If the square is ice however, the player will first be transferred into that square, and then repeat the procedure again in the same direction. This means the player will glide on the ice until either colliding with an obstacle or reaching a square filled with gravel. Gliding on ice counts only as one move.

You have almost finished your level design. In the maze, there is a goal square that you wish to reach. You still have to choose a square to be the starting point of the player. Since you do not want the level to be too easy, you want to make sure the number of moves needed to get from the starting point to the goal is sufficiently high.

Can you compute the minimum number of moves needed to get from each point in the maze to the goal? Note that move may result in the player traveling multiple squares if gliding on the ice.

-----Input-----
The first line of the input contains the two integers $3 \le C \le 1000$ and $3 \le R \le 1000$, the number of columns and rows that the maze consists of.

The next $R$ lines contains $C$ characters each, describing the maze. Each square in the maze is represented by one of the following characters:
 - a period (.) represents a gravel square
 - a pound sign (#) represents an obstacle
 - an underscore (_) represents an ice square
 - an M (M) represents the goal in the maze, which is also covered in gravel

The edges of the maze are always surrounded by obstacle squares.

-----Output-----
Output $R$ lines with $C$ integers each, one for each square, containing the number of moves needed to reach the goal.

If it is not possible to reach the target from a square, output $-1$ instead for that square.

-----Examples-----
Sample Input:
5 6
#####
#...#
#_###
#_M.#
#__.#
#####
Sample Output:
-1 -1 -1 -1 -1
-1 4 5 6 -1
-1 4 -1 -1 -1
-1 1 0 1 -1
-1 3 1 2 -1
-1 -1 -1 -1 -1

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