vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Every now and then people in the office moves teams or departments. Depending what people are doing with their time they can become more or less boring. Time to assess the current team.

```if-not:java
You will be provided with an object(staff) containing the staff names as keys, and the department they work in as values.
```

```if:java
You will be provided with an array of `Person` objects with each instance containing the name and department for a staff member.
~~~java
public class Person {
  public final String name;        // name of the staff member
  public final String department;  // department they work in
}
~~~
```

Each department has a different boredom assessment score, as follows:

accounts = 1
finance = 2 
canteen = 10 
regulation = 3 
trading = 6 
change = 6
IS = 8
retail = 5 
cleaning = 4
pissing about = 25

Depending on the cumulative score of the team, return the appropriate sentiment:

<=80: 'kill me now'
< 100 & > 80: 'i can handle this'
100 or over: 'party time!!'

The Office I - Outed
The Office III - Broken Photocopier
The Office IV - Find a Meeting Room
The Office V - Find a Chair

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Emma is really fond of integers and loves playing with them. Her friends were jealous, and to test her, one of them gave her a problem. 

Emma is given a list ${A}$ of $N$ integers and is asked a set of ${Q}$ queries. Each query is denoted by an integer ${K}$, for which you have to return the sum of product of all possible sublists having exactly ${K}$ elements. 

Emma has got stuck in this problem and you being her best friend have decided to help her write a code to solve it. Since the answers can be very large, print the answers modulo ${100003}$.

Input Format 

First line has an integer $N$, denoting the number of integers in list ${A}$. Next line contains $N$ space separated integers. The third line contains integer ${Q}$, and next ${Q}$ lines have a single integer ${K}$.

Output Format 

For each of the queries, print the corresponding answer in a new line.  

NOTE Sublist here refers to selecting ${K}$ elements from a list of $N$ elements. There will be $\left(\begin{matrix}N\\ K\end{matrix}\right)$ ways to do that, it doesn't matter if two elements are same.

Constraints 

$1\leq N\leq3\times10^4$ 

$1\leq A_i\leq10^5$ 

$1\leq Q\leq N$ 

$1\leq K\leq N$  

Sample Input #00  

3
1 2 3
2
1
2

Sample Output #00  

6
11

Sample Input #01  

3
1 2 2
1
2

Sample Output #01  

8

Explanation  

Sample #00: 

For $K=1$ possible sublists are $\{1\},\{2\},\{3\}$ so answer is $1+2+3=6$. 

For $K=2$ possible sublists are $\{1,2\},\{2,3\},\{3,1\}$ so answer is $(1\times2)+(2\times3)+(3\times1)=2+6+3=11$.

Sample #01: 

For $K=2$ possible sublists are $\{1,2\},\{2,2\},\{2,1\}$ so answer is $(1\times2)+(2\times2)+(2\times1)=2+4+2=8$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The russian intelligence agency KGB make an encryption technique to send their passwords. Originally the password is of 3 characters. After encryption the password is converted into 3 numbers A-B-C.

Now, Sherlock wants to decrypt the password encryption technique of KGB. Sherlock knows that every number  has only 2 possible values which are following:

POSSIBLE VALUES OF "A":   K, X

POSSIBLE VALUES OF "B":   G, Y

POSSIBLE VALUES OF "C":   B, Z

Help Sherlock to detect the encryption technique of the KGB and tell him the original password.
[See problem explanation for further clarifiaction]

INPUT:

The first line consist number of test cases T followed by T lines, each line consist of 3 space separated integers A, B, C.

OUTPUT

Print the correct message in format of C-C-C

Constraints:

1 ≤ T ≤ 50000

1 ≤ A, B, C ≤ 1000000000

SAMPLE INPUT
2
27 25 4
25 26 16

SAMPLE OUTPUT
K-G-B
X-Y-B

Explanation

For test case 1, the password sent is 27-25-4, then 27 can be either 'K' or 'X', similar case for 25 & 4. After applying the encryption 27 is converted into K, 25 is converted into G and 4 is converted into B.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a chess tournament in All-Right-City. n players were invited to take part in the competition. The tournament is held by the following rules:

  1. Initially, each player plays one game with every other player. There are no ties; 
  2. After that, the organizers build a complete directed graph with players as vertices. For every pair of players there is exactly one directed edge between them: the winner of their game is the startpoint of this edge and the loser is the endpoint; 
  3. After that, the organizers build a condensation of this graph. The condensation of this graph is an acyclic complete graph, therefore it has the only Hamiltonian path which consists of strongly connected components of initial graph A1 → A2 → ... → Ak. 
  4. The players from the first component A1 are placed on the first <image> places, the players from the component A2 are placed on the next <image> places, and so on. 
  5. To determine exact place of each player in a strongly connected component, all the procedures from 1 to 5 are repeated recursively inside each component, i.e. for every i = 1, 2, ..., k players from the component Ai play games with each other again, and so on; 
  6. If a component consists of a single player, then he has no more rivals, his place is already determined and the process stops. 



The players are enumerated with integers from 1 to n. The enumeration was made using results of a previous tournament. It is known that player i wins player j (i < j) with probability p.

You need to help to organize the tournament. Find the expected value of total number of games played by all the players. 

It can be shown that the answer can be represented as <image>, where P and Q are coprime integers and <image>. Print the value of P·Q - 1 modulo 998244353.

If you are not familiar with any of the terms above, you can read about them [here](https://en.wikipedia.org/wiki/Strongly_connected_component).

Input

The first line of input contains a single integer n (2 ≤ n ≤ 2000) — the number of players.

The second line contains two integers a and b (1 ≤ a < b ≤ 100) — the numerator and the denominator of fraction <image>.

Output

In the only line print the expected value of total number of games played by all the players. Print the answer using the format above.

Examples

Input

3
1 2


Output

4


Input

3
4 6


Output

142606340


Input

4
1 2


Output

598946623

Note

In the first example the expected value is 4.

In the second example the expected value is <image>.

In the third example the expected value is <image>.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A colored stripe is represented by a horizontal row of *n* square cells, each cell is pained one of *k* colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to *k* to repaint the cells.

Input Specification:
The first input line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=5·105; 2<=≤<=*k*<=≤<=26). The second line contains *n* uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first *k* English letters may be used. Each letter represents the color of the corresponding cell of the stripe.

Output Specification:
Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.

Demo Input:
['6 3\nABBACC\n', '3 2\nBBB\n']

Demo Output:
['2\nABCACA\n', '1\nBAB\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Ms Swan bought an orange in a shop. The orange consisted of *n*·*k* segments, numbered with integers from 1 to *n*·*k*. 

There were *k* children waiting for Ms Swan at home. The children have recently learned about the orange and they decided to divide it between them. For that each child took a piece of paper and wrote the number of the segment that he would like to get: the *i*-th (1<=≤<=*i*<=≤<=*k*) child wrote the number *a**i* (1<=≤<=*a**i*<=≤<=*n*·*k*). All numbers *a**i* accidentally turned out to be different.

Now the children wonder, how to divide the orange so as to meet these conditions:
 -  each child gets exactly *n* orange segments; -  the *i*-th child gets the segment with number *a**i* for sure; -  no segment goes to two children simultaneously. 
Help the children, divide the orange and fulfill the requirements, described above.

Input Specification:
The first line contains two integers *n*, *k* (1<=≤<=*n*,<=*k*<=≤<=30). The second line contains *k* space-separated integers *a*1,<=*a*2,<=...,<=*a**k* (1<=≤<=*a**i*<=≤<=*n*·*k*), where *a**i* is the number of the orange segment that the *i*-th child would like to get.

It is guaranteed that all numbers *a**i* are distinct.

Output Specification:
Print exactly *n*·*k* distinct integers. The first *n* integers represent the indexes of the segments the first child will get, the second *n* integers represent the indexes of the segments the second child will get, and so on. Separate the printed numbers with whitespaces.

You can print a child's segment indexes in any order. It is guaranteed that the answer always exists. If there are multiple correct answers, print any of them.

Demo Input:
['2 2\n4 1\n', '3 1\n2\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Misha and Changing Handles

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Misha hacked the Codeforces site. Then he decided to let all the users change their handles. A user can now change his handle any number of times. But each new handle must not be equal to any handle that is already used or that was used at some point.

Misha has a list of handle change requests. After completing the requests he wants to understand the relation between the original and the new handles of the users. Help him to do that.

Input Specification:
The first line contains integer *q* (1<=≤<=*q*<=≤<=1000), the number of handle change requests.

Next *q* lines contain the descriptions of the requests, one per line.

Each query consists of two non-empty strings *old* and *new*, separated by a space. The strings consist of lowercase and uppercase Latin letters and digits. Strings *old* and *new* are distinct. The lengths of the strings do not exceed 20.

The requests are given chronologically. In other words, by the moment of a query there is a single person with handle *old*, and handle *new* is not used and has not been used by anyone.

Output Specification:
In the first line output the integer *n* — the number of users that changed their handles at least once.

In the next *n* lines print the mapping between the old and the new handles of the users. Each of them must contain two strings, *old* and *new*, separated by a space, meaning that before the user had handle *old*, and after all the requests are completed, his handle is *new*. You may output lines in any order.

Each user who changes the handle must occur exactly once in this description.

Demo Input:
['5\nMisha ILoveCodeforces\nVasya Petrov\nPetrov VasyaPetrov123\nILoveCodeforces MikeMirzayanov\nPetya Ivanov\n']

Demo Output:
['3\nPetya Ivanov\nMisha MikeMirzayanov\nVasya VasyaPetrov123\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given two integers $a$ and $b$. Moreover, you are given a sequence $s_0, s_1, \dots, s_{n}$. All values in $s$ are integers $1$ or $-1$. It's known that sequence is $k$-periodic and $k$ divides $n+1$. In other words, for each $k \leq i \leq n$ it's satisfied that $s_{i} = s_{i - k}$.

Find out the non-negative remainder of division of $\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}$ by $10^{9} + 9$.

Note that the modulo is unusual!

Input Specification:
The first line contains four integers $n, a, b$ and $k$ $(1 \leq n \leq 10^{9}, 1 \leq a, b \leq 10^{9}, 1 \leq k \leq 10^{5})$.

The second line contains a sequence of length $k$ consisting of characters '+' and '-'. 

If the $i$-th character (0-indexed) is '+', then $s_{i} = 1$, otherwise $s_{i} = -1$.

Note that only the first $k$ members of the sequence are given, the rest can be obtained using the periodicity property.

Output Specification:
Output a single integer — value of given expression modulo $10^{9} + 9$.

Demo Input:
['2 2 3 3\n+-+\n', '4 1 5 1\n-\n']

Demo Output:
['7\n', '999999228\n']

Note:
In the first example:

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i})$ = $2^{2} 3^{0} - 2^{1} 3^{1} + 2^{0} 3^{2}$ = 7

In the second example:

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}) = -1^{4} 5^{0} - 1^{3} 5^{1} - 1^{2} 5^{2} - 1^{1} 5^{3} - 1^{0} 5^{4} = -781 \equiv 999999228 \pmod{10^{9} + 9}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are totally bored with nothing to do. You notice a pattern of spots on the wall in front of you and begin to dwell on them. There is no obvious pattern of symmetry. With time this becomes very grating, and you contemplate adding more spots to satisfy your quest for balance. For this exercise you are to resolve this situation with a computer program.

Given an array of spots with coordinates in the range from $-20000$ to $20000$, determine the fewest additional spots needed to generate a pattern with some symmetry. The symmetry can be around a point or across a line. If the symmetry is around a point, the point does not need to be a spot in the data, or even a point with integral coordinates. If the symmetry is across a line, the line may be at any angle. The coordinates of the additional spots may or may not be within the $-20000$ to $20000$ limits.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will consist of a single integer $n$ ($1 \le n \le 1000$) indicating the number of spots. Each of the next $n$ lines will hold two space-separated integers $x$ and $y$ ($-20000 \le x,y \le 20000$), which are the coordinates of a spot. The locations of all spots are guaranteed to be unique.

-----Output-----
Output a single integer, indicating the smallest number of spots which need to be added so that all of the spots are symmetric about some point, or about some line.

-----Examples-----
Sample Input:
4
0 0
1000 0
0 1000
1000 1000
Sample Output:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arkady owns a non-decreasing array $a_1, a_2, \ldots, a_n$. You are jealous of its beauty and want to destroy this property. You have a so-called XOR-gun that you can use one or more times.

In one step you can select two consecutive elements of the array, let's say $x$ and $y$, remove them from the array and insert the integer $x \oplus y$ on their place, where $\oplus$ denotes the bitwise XOR operation . Note that the length of the array decreases by one after the operation. You can't perform this operation when the length of the array reaches one.

For example, if the array is $[2, 5, 6, 8]$, you can select $5$ and $6$ and replace them with $5 \oplus 6 = 3$. The array becomes $[2, 3, 8]$.

You want the array no longer be non-decreasing. What is the minimum number of steps needed? If the array stays non-decreasing no matter what you do, print $-1$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the initial length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array. It is guaranteed that $a_i \le a_{i + 1}$ for all $1 \le i < n$.


-----Output-----

Print a single integer — the minimum number of steps needed. If there is no solution, print $-1$.


-----Examples-----

Input
4
2 5 6 8
Output
1
Input
3
1 2 3
Output
-1
Input
5
1 2 4 6 20
Output
2


-----Note-----

In the first example you can select $2$ and $5$ and the array becomes $[7, 6, 8]$.

In the second example you can only obtain arrays $[1, 1]$, $[3, 3]$ and $[0]$ which are all non-decreasing.

In the third example you can select $1$ and $2$ and the array becomes $[3, 4, 6, 20]$. Then you can, for example, select $3$ and $4$ and the array becomes $[7, 6, 20]$, which is no longer non-decreasing.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 


Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A number N is given. Divide it in half by using the binary shift operator.
Use the floor value if the result is in decimal. If the number is 1, leave it as it is.
Example 1:
Input: N = 1
Output: 1
Example 2:
Input: N = 37
Output: 18
Explaination: 37/2 = 18.5 which is in 
decimal form and whose floor value is 18.
Your Task:
You do not need to read input or print anything. Your task is to complete the function half(), which takes the number N as input parameter and returns the desired output.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constarints:
1 ≤ N ≤ 10^{9}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bachgold problem is very easy to formulate. Given a positive integer *n* represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.

Recall that integer *k* is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and *k*.

Input Specification:
The only line of the input contains a single integer *n* (2<=≤<=*n*<=≤<=100<=000).

Output Specification:
The first line of the output contains a single integer *k* — maximum possible number of primes in representation.

The second line should contain *k* primes with their sum equal to *n*. You can print them in any order. If there are several optimal solution, print any of them.

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

Demo Output:
['2\n2 3\n', '3\n2 2 2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Lexicographically Maximum Subsequence

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got string *s*, consisting of only lowercase English letters. Find its lexicographically maximum subsequence.

We'll call a non-empty string *s*[*p*1*p*2... *p**k*]<==<=*s**p*1*s**p*2... *s**p**k*(1<=≤<=*p*1<=&lt;<=*p*2<=&lt;<=...<=&lt;<=*p**k*<=≤<=|*s*|) a subsequence of string *s*<==<=*s*1*s*2... *s*|*s*|.

String *x*<==<=*x*1*x*2... *x*|*x*| is lexicographically larger than string *y*<==<=*y*1*y*2... *y*|*y*|, if either |*x*|<=&gt;<=|*y*| and *x*1<==<=*y*1,<=*x*2<==<=*y*2,<=... ,<=*x*|*y*|<==<=*y*|*y*|, or exists such number *r* (*r*<=&lt;<=|*x*|,<=*r*<=&lt;<=|*y*|), that *x*1<==<=*y*1,<=*x*2<==<=*y*2,<=... ,<=*x**r*<==<=*y**r* and *x**r*<=+<=1<=&gt;<=*y**r*<=+<=1. Characters in lines are compared like their ASCII codes.

Input Specification:
The single line contains a non-empty string *s*, consisting only of lowercase English letters. The string's length doesn't exceed 105.

Output Specification:
Print the lexicographically maximum subsequence of string *s*.

Demo Input:
['ababba\n', 'abbcbccacbbcbaaba\n']

Demo Output:
['bbba\n', 'cccccbba\n']

Note:
Let's look at samples and see what the sought subsequences look like (they are marked with uppercase bold letters).

The first sample: aBaBBA

The second sample: abbCbCCaCbbCBaaBA

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid of squares with H horizontal rows and W vertical columns. The square at the i-th row from the top and the j-th column from the left is represented as (i, j). Each square is black or white. The color of the square is given as an H-by-W matrix (a_{i, j}). If a_{i, j} is `.`, the square (i, j) is white; if a_{i, j} is `#`, the square (i, j) is black.

Snuke is compressing this grid. He will do so by repeatedly performing the following operation while there is a row or column that consists only of white squares:

* Operation: choose any one row or column that consists only of white squares, remove it and delete the space between the rows or columns.



It can be shown that the final state of the grid is uniquely determined regardless of what row or column is chosen in each operation. Find the final state of the grid.

Constraints

* 1 \leq H, W \leq 100
* a_{i, j} is `.` or `#`.
* There is at least one black square in the whole grid.

Input

Input is given from Standard Input in the following format:


H W
a_{1, 1}...a_{1, W}
:
a_{H, 1}...a_{H, W}


Output

Print the final state of the grid in the same format as input (without the numbers of rows and columns); see the samples for clarity.

Examples

Input

4 4
##.#
....
##.#
.#.#


Output

###
###
.##


Input

4 4
.#
....
.#
.#.#


Output

.##


Input

3 3
..
.#.
..#


Output

..
.#.
..#


Input

4 5
.....
.....
..#..
.....


Output




Input

7 6
......
....#.
.#....
..#...
..#...
......
.#..#.


Output

..#
..
.#.
.#.
.#

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