vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Problem

Find the angle between the two given angles θ1 and θ2. Here, the angle between them is defined as "θ1 & plus; t'when t'is the one with the smallest absolute value among the t satisfying θ1 & plus; t = θ2 − t" as shown in the figure below.

A image of angles

Constraints

The input satisfies the following conditions.

* Angle is expressed in degrees
* 0 ≤ θ1, θ2 <360
* θ1 and θ2 are integers
* | θ1 − θ2 | ≠ 180
* No input is given that gives the answer [0,0.0001] or [359.999,360)

Input

The input is given in the following format.


θ1
θ2


Output

Output the angle between θ1 and θ2 in one line in the range [0,360) in degrees. However, it must not include an error exceeding 0.0001.

Examples

Input

10
20


Output

15.0


Input

20
350


Output

5.0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The city Valera lives in is going to hold elections to the city Parliament.

The city has *n* districts and *n*<=-<=1 bidirectional roads. We know that from any district there is a path along the roads to any other district. Let's enumerate all districts in some way by integers from 1 to *n*, inclusive. Furthermore, for each road the residents decided if it is the problem road or not. A problem road is a road that needs to be repaired.

There are *n* candidates running the elections. Let's enumerate all candidates in some way by integers from 1 to *n*, inclusive. If the candidate number *i* will be elected in the city Parliament, he will perform exactly one promise — to repair all problem roads on the way from the *i*-th district to the district 1, where the city Parliament is located.

Help Valera and determine the subset of candidates such that if all candidates from the subset will be elected to the city Parliament, all problem roads in the city will be repaired. If there are several such subsets, you should choose the subset consisting of the minimum number of candidates.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=105) — the number of districts in the city.

Then *n*<=-<=1 lines follow. Each line contains the description of a city road as three positive integers *x**i*, *y**i*, *t**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=*n*, 1<=≤<=*t**i*<=≤<=2) — the districts connected by the *i*-th bidirectional road and the road type. If *t**i* equals to one, then the *i*-th road isn't the problem road; if *t**i* equals to two, then the *i*-th road is the problem road.

It's guaranteed that the graph structure of the city is a tree.

Output Specification:
In the first line print a single non-negative number *k* — the minimum size of the required subset of candidates. Then on the second line print *k* space-separated integers *a*1,<=*a*2,<=... *a**k* — the numbers of the candidates that form the required subset. If there are multiple solutions, you are allowed to print any of them.

Demo Input:
['5\n1 2 2\n2 3 2\n3 4 2\n4 5 2\n', '5\n1 2 1\n2 3 2\n2 4 1\n4 5 1\n', '5\n1 2 2\n1 3 2\n1 4 2\n1 5 2\n']

Demo Output:
['1\n5 \n', '1\n3 \n', '4\n5 4 3 2 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n lights aligned in a row. These lights are numbered 1 to n from left to right. Initially some of the lights are switched on. Shaass wants to switch all the lights on. At each step he can switch a light on (this light should be switched off at that moment) if there's at least one adjacent light which is already switched on. 

He knows the initial state of lights and he's wondering how many different ways there exist to switch all the lights on. Please find the required number of ways modulo 1000000007 (10^9 + 7).


-----Input-----

The first line of the input contains two integers n and m where n is the number of lights in the sequence and m is the number of lights which are initially switched on, (1 ≤ n ≤ 1000, 1 ≤ m ≤ n). The second line contains m distinct integers, each between 1 to n inclusive, denoting the indices of lights which are initially switched on.


-----Output-----

In the only line of the output print the number of different possible ways to switch on all the lights modulo 1000000007 (10^9 + 7).


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

Output
1

Input
4 2
1 4

Output
2

Input
11 2
4 8

Output
6720

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a string s, consisting of capital Latin letters. Let's denote its current length as |s|. During one move it is allowed to apply one of the following operations to it: 

  * INSERT pos ch — insert a letter ch in the string s in the position pos (1 ≤ pos ≤ |s| + 1, A ≤ ch ≤ Z). The letter ch becomes the pos-th symbol of the string s, at that the letters shift aside and the length of the string increases by 1. 
  * DELETE pos — delete a character number pos (1 ≤ pos ≤ |s|) from the string s. At that the letters shift together and the length of the string decreases by 1. 
  * REPLACE pos ch — the letter in the position pos of the line s is replaced by ch (1 ≤ pos ≤ |s|, A ≤ ch ≤ Z). At that the length of the string does not change. 



Your task is to find in which minimal number of moves one can get a t string from an s string. You should also find the sequence of actions leading to the required results.

Input

The first line contains s, the second line contains t. The lines consist only of capital Latin letters, their lengths are positive numbers from 1 to 1000.

Output

In the first line print the number of moves k in the given sequence of operations. The number should be the minimal possible one. Then print k lines containing one operation each. Print the operations in the format, described above. If there are several solutions, print any of them.

Examples

Input

ABA
ABBBA


Output

2
INSERT 3 B
INSERT 4 B


Input

ACCEPTED
WRONGANSWER


Output

10
REPLACE 1 W
REPLACE 2 R
REPLACE 3 O
REPLACE 4 N
REPLACE 5 G
REPLACE 6 A
INSERT 7 N
INSERT 8 S
INSERT 9 W
REPLACE 11 R

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are going to drive from their home to a theater for a date. They are very challenging - they have no maps with them even though they don’t know the route at all (since they have just moved to their new home). Yes, they will be going just by their feeling.

The town they drive can be considered as an undirected graph with a number of intersections (vertices) and roads (edges). Each intersection may or may not have a sign. On intersections with signs, Alice and Bob will enter the road for the shortest route. When there is more than one such roads, they will go into one of them at random.

On intersections without signs, they will just make a random choice. Each random selection is made with equal probabilities. They can even choose to go back to the road they have just come along, on a random selection.

Calculate the expected distance Alice and Bob will drive before reaching the theater.



Input

The input consists of multiple datasets. Each dataset has the following format:

n s t
q1 q2 ... qn
a11 a12 ... a1n
a21 a22 ... a2n
.
.
.
an1 an2 ... ann


n is the number of intersections (n ≤ 100). s and t are the intersections the home and the theater are located respectively (1 ≤ s, t ≤ n, s ≠ t); qi (for 1 ≤ i ≤ n) is either 1 or 0, where 1 denotes there is a sign at the i-th intersection and 0 denotes there is not; aij (for 1 ≤ i, j ≤ n) is a positive integer denoting the distance of the road connecting the i-th and j-th intersections, or 0 indicating there is no road directly connecting the intersections. The distance of each road does not exceed 10.

Since the graph is undirectional, it holds aij = aji for any 1 ≤ i, j ≤ n. There can be roads connecting the same intersection, that is, it does not always hold aii = 0. Also, note that the graph is not always planar.

The last dataset is followed by a line containing three zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the expected distance accurate to 10-8 , or "impossible" (without quotes) if there is no route to get to the theater. The distance may be printed with any number of digits after the decimal point.

Example

Input

5 1 5
1 0 1 0 0
0 2 1 0 0
2 0 0 1 0
1 0 0 1 0
0 1 1 0 1
0 0 0 1 0
0 0 0


Output

8.50000000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pashmak decided to give Parmida a pair of flowers from the garden. There are *n* flowers in the garden and the *i*-th of them has a beauty number *b**i*. Parmida is a very strange girl so she doesn't want to have the two most beautiful flowers necessarily. She wants to have those pairs of flowers that their beauty difference is maximal possible!

Your task is to write a program which calculates two things:
 1.  The maximum beauty difference of flowers that Pashmak can give to Parmida. 1.  The number of ways that Pashmak can pick the flowers. Two ways are considered different if and only if there is at least one flower that is chosen in the first way and not chosen in the second way.

Input Specification:
The first line of the input contains *n* (2<=≤<=*n*<=≤<=2·105). In the next line there are *n* space-separated integers *b*1, *b*2, ..., *b**n* (1<=≤<=*b**i*<=≤<=109).

Output Specification:
The only line of output should contain two integers. The maximum beauty difference and the number of ways this may happen, respectively.

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

Demo Output:
['1 1', '4 1', '2 4']

Note:
In the third sample the maximum beauty difference is 2 and there are 4 ways to do this:
 1.  choosing the first and the second flowers; 1.  choosing the first and the fifth flowers; 1.  choosing the fourth and the second flowers; 1.  choosing the fourth and the fifth flowers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s which contains lowercase english letters and dot sign (.) (e.g:   abc.d.ee.g). Your task is to replace substring '..' with a substring '.' in the given string i.e the string should not contain 2 consecutive dot signs. You need to calculate the no. of replacements required for this task.

First line contains two integers L denoting length of string and N denoting no. of queries on the string. Second line of input contains string s
Each of the next N lines contains 2 inputs    k(integer) and p(lowercase letter/dot sign).
Your task is to replace k th letter in given string with given letter p and count the replacements.
For the next query use the string modified in previous query.

SAMPLE INPUT
4 4
.cc.
2 .
3 .
2 a
1 a

SAMPLE OUTPUT
1
3
1
1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given three integers $a$, $b$ and $x$. Your task is to construct a binary string $s$ of length $n = a + b$ such that there are exactly $a$ zeroes, exactly $b$ ones and exactly $x$ indices $i$ (where $1 \le i &lt; n$) such that $s_i \ne s_{i + 1}$. It is guaranteed that the answer always exists.

For example, for the string "01010" there are four indices $i$ such that $1 \le i &lt; n$ and $s_i \ne s_{i + 1}$ ($i = 1, 2, 3, 4$). For the string "111001" there are two such indices $i$ ($i = 3, 5$).

Recall that binary string is a non-empty sequence of characters where each character is either 0 or 1.

Input Specification:
The first line of the input contains three integers $a$, $b$ and $x$ ($1 \le a, b \le 100, 1 \le x &lt; a + b)$.

Output Specification:
Print only one string $s$, where $s$ is any binary string satisfying conditions described above. It is guaranteed that the answer always exists.

Demo Input:
['2 2 1\n', '3 3 3\n', '5 3 6\n']

Demo Output:
['1100\n', '101100\n', '01010100\n']

Note:
All possible answers for the first example: 
 -  1100; -  0011. 
All possible answers for the second example: 
 -  110100; -  101100; -  110010; -  100110; -  011001; -  001101; -  010011; -  001011.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today, as a friendship gift, Bakry gave Badawy $n$ integers $a_1, a_2, \dots, a_n$ and challenged him to choose an integer $X$ such that the value $\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$ is minimum possible, where $\oplus$ denotes the bitwise XOR operation.

As always, Badawy is too lazy, so you decided to help him and find the minimum possible value of $\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$.


-----Input-----

The first line contains integer $n$ ($1\le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2^{30}-1$).


-----Output-----

Print one integer — the minimum possible value of $\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$.


-----Examples-----
Input
3
1 2 3

Output
2

Input
2
1 5

Output
4



-----Note-----

In the first sample, we can choose $X = 3$.

In the second sample, we can choose $X = 5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There was an explorer Henry Nelson traveling all over the world. One day he reached an ancient building. He decided to enter this building for his interest, but its entrance seemed to be locked by a strange security system.

There were some black and white panels placed on a line at equal intervals in front of the entrance, and a strange machine with a cryptogram attached. After a while, he managed to read this cryptogram: this entrance would be unlocked when the panels were rearranged in a certain order, and he needed to use this special machine to change the order of panels.

All he could do with this machine was to swap arbitrary pairs of panels. Each swap could be performed by the following steps:

* move the machine to one panel and mark it;
* move the machine to another panel and again mark it; then
* turn on a special switch of the machine to have the two marked panels swapped.



It was impossible to have more than two panels marked simultaneously. The marks would be erased every time the panels are swapped.

He had to change the order of panels by a number of swaps to enter the building. Unfortunately, however, the machine was so heavy that he didn’t want to move it more than needed. Then which steps could be the best?

Your task is to write a program that finds the minimum cost needed to rearrange the panels, where moving the machine between adjacent panels is defined to require the cost of one. You can arbitrarily choose the initial position of the machine, and don’t have to count the cost for moving the machine to that position.



Input

The input consists of multiple datasets.

Each dataset consists of three lines. The first line contains an integer N, which indicates the number of panels (2 ≤ N ≤ 16). The second and third lines contain N characters each, and describe the initial and final orders of the panels respectively. Each character in these descriptions is either ‘B’ (for black) or ‘W’ (for white) and denotes the color of the panel. The panels of the same color should not be distinguished.

The input is terminated by a line with a single zero.

Output

For each dataset, output the minimum cost on a line. You can assume that there is at least one way to change the order of the panels from the initial one to the final one.

Example

Input

4
WBWB
BWBW
8
WWWWBWBB
WWBBWBWW
0


Output

3
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arkady is playing Battleship. The rules of this game aren't really important.

There is a field of $n \times n$ cells. There should be exactly one $k$-decker on the field, i. e. a ship that is $k$ cells long oriented either horizontally or vertically. However, Arkady doesn't know where it is located. For each cell Arkady knows if it is definitely empty or can contain a part of the ship.

Consider all possible locations of the ship. Find such a cell that belongs to the maximum possible number of different locations of the ship.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the size of the field and the size of the ship.

The next $n$ lines contain the field. Each line contains $n$ characters, each of which is either '#' (denotes a definitely empty cell) or '.' (denotes a cell that can belong to the ship).


-----Output-----

Output two integers — the row and the column of a cell that belongs to the maximum possible number of different locations of the ship.

If there are multiple answers, output any of them. In particular, if no ship can be placed on the field, you can output any cell.


-----Examples-----
Input
4 3
#..#
#.#.
....
.###

Output
3 2

Input
10 4
#....##...
.#...#....
..#..#..#.
...#.#....
.#..##.#..
.....#...#
...#.##...
.#...#.#..
.....#..#.
...#.#...#

Output
6 1

Input
19 6
##..............###
#......#####.....##
.....#########.....
....###########....
...#############...
..###############..
.#################.
.#################.
.#################.
.#################.
#####....##....####
####............###
####............###
#####...####...####
.#####..####..#####
...###........###..
....###########....
.........##........
#.................#

Output
1 8



-----Note-----

The picture below shows the three possible locations of the ship that contain the cell $(3, 2)$ in the first sample. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a sequence of length N: A_1, A_2, ..., A_N. Initially, this sequence is a permutation of 1, 2, ..., N.
On this sequence, Snuke can perform the following operation:
 - Choose K consecutive elements in the sequence. Then, replace the value of each chosen element with the minimum value among the chosen elements.
Snuke would like to make all the elements in this sequence equal by repeating the operation above some number of times.
Find the minimum number of operations required.
It can be proved that, Under the constraints of this problem, this objective is always achievable.

-----Constraints-----
 - 2 \leq K \leq N \leq 100000
 - A_1, A_2, ..., A_N is a permutation of 1, 2, ..., N.

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 ... A_N

-----Output-----
Print the minimum number of operations required.

-----Sample Input-----
4 3
2 3 1 4

-----Sample Output-----
2

One optimal strategy is as follows:
 - In the first operation, choose the first, second and third elements. The sequence A becomes 1, 1, 1, 4.
 - In the second operation, choose the second, third and fourth elements. The sequence A becomes 1, 1, 1, 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mohit(Ex GenSec ) is the most active member of the roasting club who loves giving tasks to other members. One day he observed that none of the members were paying attention to the online classes, so he decided to have some fun and overcome the boring lectures. He wrote N numbers on the virtual board (where the first number is 1, the last one is N and the ith number being i).
Then he asked M questions to every other member of the club. In each question, a number K was given by Mohit and the members had to give a single integer as an answer which will be the sum of all numbers present on the whiteboard.
There are some conditions that every member has to follow while answering.
- If K is already present on the whiteboard then swap the first and last number.
- Otherwise, replace the last number with K.

-----Input:-----
- First-line will consist of space-separated integers N and M. The board will contain the list of numbers from 1 to N and M is the number of questions that Mohit will ask.
- Next M lines contain the number Ki, which will be provided by Mohit and (1<=i<=M).

-----Output:-----
For each question, report the sum of all integers present

-----Constraints-----
- $1 \leq N,M \leq 1000000$
- $2 \leq K \leq 10^9$

-----Sample Input:-----
5 4
7
12 
10 
1  

-----Sample Output:-----
17
22  
20
20

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Niwel is a little golden bear. As everyone knows, bears live in forests, but Niwel got tired of seeing all the trees so he decided to move to the city.

In the city, Niwel took on a job managing bears to deliver goods. The city that he lives in can be represented as a directed graph with n nodes and m edges. Each edge has a weight capacity. A delivery consists of a bear carrying weights with their bear hands on a simple path from node 1 to node n. The total weight that travels across a particular edge must not exceed the weight capacity of that edge.

Niwel has exactly x bears. In the interest of fairness, no bear can rest, and the weight that each bear carries must be exactly the same. However, each bear may take different paths if they like.

Niwel would like to determine, what is the maximum amount of weight he can deliver (it's the sum of weights carried by bears). Find the maximum weight.

Input

The first line contains three integers n, m and x (2 ≤ n ≤ 50, 1 ≤ m ≤ 500, 1 ≤ x ≤ 100 000) — the number of nodes, the number of directed edges and the number of bears, respectively.

Each of the following m lines contains three integers ai, bi and ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 1 000 000). This represents a directed edge from node ai to bi with weight capacity ci. There are no self loops and no multiple edges from one city to the other city. More formally, for each i and j that i ≠ j it's guaranteed that ai ≠ aj or bi ≠ bj. It is also guaranteed that there is at least one path from node 1 to node n.

Output

Print one real value on a single line — the maximum amount of weight Niwel can deliver if he uses exactly x bears. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if <image>.

Examples

Input

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


Output

1.5000000000


Input

5 11 23
1 2 3
2 3 4
3 4 5
4 5 6
1 3 4
2 4 5
3 5 6
1 4 2
2 5 3
1 5 2
3 2 30


Output

10.2222222222

Note

In the first sample, Niwel has three bears. Two bears can choose the path <image>, while one bear can choose the path <image>. Even though the bear that goes on the path <image> can carry one unit of weight, in the interest of fairness, he is restricted to carry 0.5 units of weight. Thus, the total weight is 1.5 units overall. Note that even though Niwel can deliver more weight with just 2 bears, he must use exactly 3 bears on this day.

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