vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Double Profiles

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have been offered a job in a company developing a large social network. Your first task is connected with searching profiles that most probably belong to the same user.

The social network contains *n* registered profiles, numbered from 1 to *n*. Some pairs there are friends (the "friendship" relationship is mutual, that is, if *i* is friends with *j*, then *j* is also friends with *i*). Let's say that profiles *i* and *j* (*i*<=≠<=*j*) are doubles, if for any profile *k* (*k*<=≠<=*i*, *k*<=≠<=*j*) one of the two statements is true: either *k* is friends with *i* and *j*, or *k* isn't friends with either of them. Also, *i* and *j* can be friends or not be friends.

Your task is to count the number of different unordered pairs (*i*,<=*j*), such that the profiles *i* and *j* are doubles. Note that the pairs are unordered, that is, pairs (*a*,<=*b*) and (*b*,<=*a*) are considered identical.

Input Specification:
The first line contains two space-separated integers *n* and *m* (1<=≤<=*n*<=≤<=106, 0<=≤<=*m*<=≤<=106), — the number of profiles and the number of pairs of friends, correspondingly. 

Next *m* lines contains descriptions of pairs of friends in the format "*v* *u*", where *v* and *u* (1<=≤<=*v*,<=*u*<=≤<=*n*,<=*v*<=≠<=*u*) are numbers of profiles that are friends with each other. It is guaranteed that each unordered pair of friends occurs no more than once and no profile is friends with itself.

Output Specification:
Print the single integer — the number of unordered pairs of profiles that are doubles. 

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the %I64d specificator.

Demo Input:
['3 3\n1 2\n2 3\n1 3\n', '3 0\n', '4 1\n1 3\n']

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

Note:
In the first and second sample any two profiles are doubles.

In the third sample the doubles are pairs of profiles (1, 3) and (2, 4).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a harder version of the problem. In this version, n ≤ 7.

Marek is working hard on creating strong test cases to his new algorithmic problem. Do you want to know what it is? Nah, we're not telling you. However, we can tell you how he generates test cases.

Marek chooses an integer n and n^2 integers p_{ij} (1 ≤ i ≤ n, 1 ≤ j ≤ n). He then generates a random bipartite graph with 2n vertices. There are n vertices on the left side: ℓ_1, ℓ_2, ..., ℓ_n, and n vertices on the right side: r_1, r_2, ..., r_n. For each i and j, he puts an edge between vertices ℓ_i and r_j with probability p_{ij} percent.

It turns out that the tests will be strong only if a perfect matching exists in the generated graph. What is the probability that this will occur?

It can be shown that this value can be represented as P/Q where P and Q are coprime integers and Q not≡ 0 \pmod{10^9+7}. Let Q^{-1} be an integer for which Q ⋅ Q^{-1} ≡ 1 \pmod{10^9+7}. Print the value of P ⋅ Q^{-1} modulo 10^9+7.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 7). The following n lines describe the probabilities of each edge appearing in the graph. The i-th of the lines contains n integers p_{i1}, p_{i2}, ..., p_{in} (0 ≤ p_{ij} ≤ 100); p_{ij} denotes the probability, in percent, of an edge appearing between ℓ_i and r_j.

Output

Print a single integer — the probability that the perfect matching exists in the bipartite graph, written as P ⋅ Q^{-1} \pmod{10^9+7} for P, Q defined above.

Examples

Input


2
50 50
50 50


Output


937500007


Input


3
3 1 4
1 5 9
2 6 5


Output


351284554

Note

In the first sample test, each of the 16 graphs below is equally probable. Out of these, 7 have a perfect matching:

<image>

Therefore, the probability is equal to 7/16. As 16 ⋅ 562 500 004 = 1 \pmod{10^9+7}, the answer to the testcase is 7 ⋅ 562 500 004 mod{(10^9+7)} = 937 500 007.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer $n$. You have to calculate the number of binary (consisting of characters 0 and/or 1) strings $s$ meeting the following constraints.

For every pair of integers $(i, j)$ such that $1 \le i \le j \le n$, an integer $a_{i,j}$ is given. It imposes the following constraint on the string $s_i s_{i+1} s_{i+2} \dots s_j$:

if $a_{i,j} = 1$, all characters in $s_i s_{i+1} s_{i+2} \dots s_j$ should be the same;

if $a_{i,j} = 2$, there should be at least two different characters in $s_i s_{i+1} s_{i+2} \dots s_j$;

if $a_{i,j} = 0$, there are no additional constraints on the string $s_i s_{i+1} s_{i+2} \dots s_j$.

Count the number of binary strings $s$ of length $n$ meeting the aforementioned constraints. Since the answer can be large, print it modulo $998244353$.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 100$).

Then $n$ lines follow. The $i$-th of them contains $n-i+1$ integers $a_{i,i}, a_{i,i+1}, a_{i,i+2}, \dots, a_{i,n}$ ($0 \le a_{i,j} \le 2$).


-----Output-----

Print one integer — the number of strings meeting the constraints, taken modulo $998244353$.


-----Examples-----

Input
3
1 0 2
1 0
1
Output
6
Input
3
1 1 2
1 0
1
Output
2
Input
3
1 2 1
1 0
1
Output
0
Input
3
2 0 2
0 1
1
Output
0


-----Note-----

In the first example, the strings meeting the constraints are 001, 010, 011, 100, 101, 110.

In the second example, the strings meeting the constraints are 001, 110.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You went shopping to buy cakes and donuts with X yen (the currency of Japan).
First, you bought one cake for A yen at a cake shop.
Then, you bought as many donuts as possible for B yen each, at a donut shop.
How much do you have left after shopping?

-----Constraints-----
 - 1 \leq A, B \leq 1 000
 - A + B \leq X \leq 10 000
 - X, A and B are integers.

-----Input-----
Input is given from Standard Input in the following format:
X
A
B

-----Output-----
Print the amount you have left after shopping.

-----Sample Input-----
1234
150
100

-----Sample Output-----
84

You have 1234 - 150 = 1084 yen left after buying a cake.
With this amount, you can buy 10 donuts, after which you have 84 yen left.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* points on a straight line, and the *i*-th point among them is located at *x**i*. All these coordinates are distinct.

Determine the number *m* — the smallest number of points you should add on the line to make the distances between all neighboring points equal.

Input Specification:
The first line contains a single integer *n* (3<=≤<=*n*<=≤<=100<=000) — the number of points.

The second line contains a sequence of integers *x*1,<=*x*2,<=...,<=*x**n* (<=-<=109<=≤<=*x**i*<=≤<=109) — the coordinates of the points. All these coordinates are distinct. The points can be given in an arbitrary order.

Output Specification:
Print a single integer *m* — the smallest number of points you should add on the line to make the distances between all neighboring points equal.

Demo Input:
['3\n-5 10 5\n', '6\n100 200 400 300 600 500\n', '4\n10 9 0 -1\n']

Demo Output:
['1\n', '0\n', '8\n']

Note:
In the first example you can add one point with coordinate 0.

In the second example the distances between all neighboring points are already equal, so you shouldn't add anything.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The postal service is interested in cutting costs as an alternative to raising the postage rates. One way to do this is by minimizing the distance traveled when delivering mail from the post office to all the required locations and returning to the post office. It may be that all the mail to be delivered does not fit on the mail truck at once, in which case the distance traveled by the truck must include travel back to the post office to reload. For simplicity, we assume a one dimensional world with the post office at the origin, and delivery locations each identified by a single coordinate. As an example, suppose a postal truck can carry up to $100$ letters and that $50$ letters need to be delivered to location $-10$, that $175$ need to be delivered to location $10$, and $20$ delivered to location $25$. A maximally efficient plan would be:

Deliver the $50$ letters to location $-10$ (travel $2 \cdot 10$), the first $100$ letters to location $10$ (travel $2 \cdot 10$), the remaining $75$ letters to location $10$ while on the way to delivering the $20$ to location $25$ (travel $2 \cdot 25$). The total round-trip distance traveled is $90$.

-----Input-----
The first line contains two integers, $N$ and $K$, where $3 \leq N \leq 1000$ is the number of delivery addresses on the route, and $1 \leq K \leq 10000$ is the carrying capacity of the postal truck. Each of the following $N$ lines will contain two integers $x_ j$ and $t_ j$, the location of a delivery and the number of letters to deliver there, where $-1500 \leq x_1 < x_2 < \cdots < x_ N \leq 1500$ and $1 \leq t_ j \leq 800$ for all $j$. All delivery locations are nonzero (that is, none are at the post office).

-----Output-----
Output the minimum total travel distance needed to deliver all the letters and return to the post office.

-----Examples-----
Sample Input:
3 100
-10 50
10 175
25 20
Sample Output:
90

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tokitsukaze is playing a game derivated from Japanese mahjong. In this game, she has three tiles in her hand. Each tile she owns is a suited tile, which means it has a suit (manzu, pinzu or souzu) and a number (a digit ranged from $1$ to $9$). In this problem, we use one digit and one lowercase letter, which is the first character of the suit, to represent a suited tile. All possible suited tiles are represented as 1m, 2m, $\ldots$, 9m, 1p, 2p, $\ldots$, 9p, 1s, 2s, $\ldots$, 9s.

In order to win the game, she must have at least one mentsu (described below) in her hand, so sometimes she should draw extra suited tiles. After drawing a tile, the number of her tiles increases by one. She can draw any tiles she wants, including those already in her hand.

Do you know the minimum number of extra suited tiles she needs to draw so that she can win?

Here are some useful definitions in this game:  A mentsu, also known as meld, is formed by a koutsu or a shuntsu;  A koutsu, also known as triplet, is made of three identical tiles, such as [1m, 1m, 1m], however, [1m, 1p, 1s] or [1m, 4m, 7m] is NOT a koutsu;  A shuntsu, also known as sequence, is made of three sequential numbered tiles in the same suit, such as [1m, 2m, 3m] and [5s, 7s, 6s], however, [9m, 1m, 2m] or [1m, 2p, 3s] is NOT a shuntsu. 

Some examples:   [2m, 3p, 2s, 4m, 1s, 2s, 4s] — it contains no koutsu or shuntsu, so it includes no mentsu;  [4s, 3m, 3p, 4s, 5p, 4s, 5p] — it contains a koutsu, [4s, 4s, 4s], but no shuntsu, so it includes a mentsu;  [5p, 5s, 9m, 4p, 1s, 7p, 7m, 6p] — it contains no koutsu but a shuntsu, [5p, 4p, 6p] or [5p, 7p, 6p], so it includes a mentsu. 

Note that the order of tiles is unnecessary and you can assume the number of each type of suited tiles she can draw is infinite.


-----Input-----

The only line contains three strings — the tiles in Tokitsukaze's hand. For each string, the first character is a digit ranged from $1$ to $9$ and the second character is m, p or s.


-----Output-----

Print a single integer — the minimum number of extra suited tiles she needs to draw.


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

Output
0

Input
9m 9m 9m

Output
0

Input
3p 9m 2p

Output
1



-----Note-----

In the first example, Tokitsukaze already has a shuntsu.

In the second example, Tokitsukaze already has a koutsu.

In the third example, Tokitsukaze can get a shuntsu by drawing one suited tile — 1p or 4p. The resulting tiles will be [3p, 9m, 2p, 1p] or [3p, 9m, 2p, 4p].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Adam is standing at point $(a,b)$ in an infinite 2D grid. He wants to know if he can reach point $(x,y)$ or not. The only operation he can do is to move to point $(a+b,b),(a,a+b),(a-b,b),\text{or}(a,b-a)$ from some point $(a,b)$. It is given that he can move to any point on this 2D grid, i.e., the points having positive or negative $\mbox{X}$(or $\mathbf{Y}$) co-ordinates.  

Tell Adam whether he can reach $(x,y)$ or not.

Input Format

The first line contains an integer, $\mathbf{T}$, followed by $\mathbf{T}$ lines, each containing $4$ space-separated integers i.e. $\boldsymbol{a}$, $\boldsymbol{b}$, $\boldsymbol{x}$ and $y$.  

Constraints

$1\leq T\leq1000$  
$1\leq a,b,x,y\leq10^{18}$ 

Output Format

For each test case, display YES or NO that indicates if Adam can reach $(x,y)$ or not.  

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

Sample Output
YES
YES
NO

Explanation

(1,1) -> (2,1) -> (2,3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program to find the remainder when an integer A is divided by an integer B.

-----Input-----

The first line contains an integer T, the total number of test cases. Then T lines follow, each line contains two Integers A and B. 

-----Output-----
For each test case, find the remainder when A is divided by  B, and display it in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ A,B ≤ 10000

-----Example-----
Input
3 
1 2
100 200
40 15

Output
1
100
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary array arr of size N and an integer M. Find the maximum number of consecutive 1's produced by flipping at most M 0's.
 
Example 1:
Input:
N = 3
arr[] = {1, 0, 1}
M = 1
Output:
3
Explanation:
Maximum subarray is of size 3
which can be made subarray of all 1 after
flipping one zero to 1.
Example 2:
Input:
N = 11
arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}
M = 2
Output:
8
Explanation:
Maximum subarray is of size 8
which can be made subarray of all 1 after
flipping two zeros to 1.
 
Your Task:
Complete the function findZeroes() which takes array arr and two integers n, m, as input parameters and returns an integer denoting the answer. 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{7}
0 <= M <= N
0 <= arr_{i} <= 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given array a_1, a_2, ..., a_n. You need to split it into k subsegments (so every element is included in exactly one subsegment).

The weight of a subsegment a_l, a_{l+1}, ..., a_r is equal to (r - l + 1) ⋅ max_{l ≤ i ≤ r}(a_i). The weight of a partition is a total weight of all its segments.

Find the partition of minimal weight.

Input

The first line contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^4, 1 ≤ k ≤ min(100, n)) — the length of the array a and the number of subsegments in the partition.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^4) — the array a.

Output

Print single integer — the minimal weight among all possible partitions.

Examples

Input


4 2
6 1 7 4


Output


25


Input


4 3
6 1 7 4


Output


21


Input


5 4
5 1 5 1 5


Output


21

Note

The optimal partition in the first example is next: 6 1 7 \bigg| 4.

The optimal partition in the second example is next: 6 \bigg| 1 \bigg| 7 4.

One of the optimal partitions in the third example is next: 5 \bigg| 1 5 \bigg| 1 \bigg| 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mishka wants to buy some food in the nearby shop. Initially, he has $s$ burles on his card. 

Mishka can perform the following operation any number of times (possibly, zero): choose some positive integer number $1 \le x \le s$, buy food that costs exactly $x$ burles and obtain $\lfloor\frac{x}{10}\rfloor$ burles as a cashback (in other words, Mishka spends $x$ burles and obtains $\lfloor\frac{x}{10}\rfloor$ back). The operation $\lfloor\frac{a}{b}\rfloor$ means $a$ divided by $b$ rounded down.

It is guaranteed that you can always buy some food that costs $x$ for any possible value of $x$.

Your task is to say the maximum number of burles Mishka can spend if he buys food optimally.

For example, if Mishka has $s=19$ burles then the maximum number of burles he can spend is $21$. Firstly, he can spend $x=10$ burles, obtain $1$ burle as a cashback. Now he has $s=10$ burles, so can spend $x=10$ burles, obtain $1$ burle as a cashback and spend it too.

You have to answer $t$ independent test cases.


-----Input-----

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

The next $t$ lines describe test cases. Each test case is given on a separate line and consists of one integer $s$ ($1 \le s \le 10^9$) — the number of burles Mishka initially has.


-----Output-----

For each test case print the answer on it — the maximum number of burles Mishka can spend if he buys food optimally.


-----Example-----
Input
6
1
10
19
9876
12345
1000000000

Output
1
11
21
10973
13716
1111111111

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem K Counting Cycles

Given an undirected graph, count the number of simple cycles in the graph. Here, a simple cycle is a connected subgraph all of whose vertices have degree exactly two.

Input

The input consists of a single test case of the following format.


$n$ $m$
$u_1$ $v_1$
...
$u_m$ $v_m$


A test case represents an undirected graph $G$.

The first line shows the number of vertices $n$ ($3 \leq n \leq 100 000$) and the number of edges $m$ ($n - 1 \leq m \leq n + 15$). The vertices of the graph are numbered from $1$ to $n$.

The edges of the graph are specified in the following $m$ lines. Two integers $u_i$ and $v_i$ in the $i$-th line of these m lines mean that there is an edge between vertices $u_i$ and $v_i$. Here, you can assume that $u_i < v_i$ and thus there are no self loops.

For all pairs of $i$ and $j$ ($i \ne j$), either $u_i \ne u_j$ or $v_i \ne v_j$ holds. In other words, there are no parallel edges.

You can assume that $G$ is connected.

Output

The output should be a line containing a single number that is the number of simple cycles in the graph.

Sample Input 1


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


Sample Output 1


3


Sample Input 2


7 9
1 2
1 3
2 4
2 5
3 6
3 7
2 3
4 5
6 7


Sample Output 2


3


Sample Input 3


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


Sample Output 3


7






Example

Input

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


Output

3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dima has a hamsters farm. Soon *N* hamsters will grow up on it and Dima will sell them in a city nearby.

Hamsters should be transported in boxes. If some box is not completely full, the hamsters in it are bored, that's why each box should be completely full with hamsters.

Dima can buy boxes at a factory. The factory produces boxes of *K* kinds, boxes of the *i*-th kind can contain in themselves *a**i* hamsters. Dima can buy any amount of boxes, but he should buy boxes of only one kind to get a wholesale discount.

Of course, Dima would buy boxes in such a way that each box can be completely filled with hamsters and transported to the city. If there is no place for some hamsters, Dima will leave them on the farm.

Find out how many boxes and of which type should Dima buy to transport maximum number of hamsters.

Input Specification:
The first line contains two integers *N* and *K* (0<=≤<=*N*<=≤<=1018, 1<=≤<=*K*<=≤<=105) — the number of hamsters that will grow up on Dima's farm and the number of types of boxes that the factory produces.

The second line contains *K* integers *a*1, *a*2, ..., *a**K* (1<=≤<=*a**i*<=≤<=1018 for all *i*) — the capacities of boxes.

Output Specification:
Output two integers: the type of boxes that Dima should buy and the number of boxes of that type Dima should buy. Types of boxes are numbered from 1 to *K* in the order they are given in input.

If there are many correct answers, output any of them.

Demo Input:
['19 3\n5 4 10\n', '28 3\n5 6 30\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Laura really hates people using acronyms in her office and wants to force her colleagues to remove all acronyms before emailing her. She wants you to build a system that will edit out all known acronyms or else will notify the sender if unknown acronyms are present.

Any combination of three or more letters in upper case will be considered an acronym. Acronyms will not be combined with lowercase letters, such as in the case of 'KPIs'. They will be kept isolated as a word/words within a string.

For any string: 

All instances of 'KPI' must become "key performance indicators" 
All instances of 'EOD' must become "the end of the day" 
All instances of 'TBD' must become "to be decided"
All instances of 'WAH' must become "work at home"
All instances of 'IAM' must become "in a meeting"
All instances of 'OOO' must become "out of office"
All instances of 'NRN' must become "no reply necessary"
All instances of 'CTA' must become "call to action"
All instances of 'SWOT' must become "strengths, weaknesses, opportunities and threats"
If there are any unknown acronyms in the string, Laura wants you to return only the message:
'[acronym] is an acronym. I do not like acronyms. Please remove them from your email.'
So if the acronym in question was 'BRB', you would return the string:
'BRB is an acronym. I do not like acronyms. Please remove them from your email.'
If there is more than one unknown acronym in the string, return only the first in your answer.

If all acronyms can be replaced with full words according to the above, however, return only the altered string.

If this is the case, ensure that sentences still start with capital letters. '!' or '?' will not be used.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let G be a simple graph. Let W be a non-empty subset of vertices. Then W is almost-k-uniform if for each pair of distinct vertices u,v ∈ W the distance between u and v is either k or k+1.

You are given a tree on n vertices. For each i between 1 and n, find the maximum size of an almost-i-uniform set.

Input

The first line contains a single integer n (2 ≤ n ≤ 5 ⋅ 10^5) – the number of vertices of the tree.

Then n-1 lines follows, the i-th of which consisting of two space separated integers u_i, v_i (1 ≤ u_i, v_i ≤ n) meaning that there is an edge between vertices u_i and v_i. 

It is guaranteed that the given graph is tree. 

Output

Output a single line containing n space separated integers a_i, where a_i is the maximum size of an almost-i-uniform set.

Examples

Input


5
1 2
1 3
1 4
4 5


Output


4 3 2 1 1


Input


6
1 2
1 3
1 4
4 5
4 6


Output


4 4 2 1 1 1

Note

Consider the first example. 

  * The only maximum almost-1-uniform set is \{1, 2, 3, 4\}. 
  * One of the maximum almost-2-uniform sets is or \{2, 3, 5\}, another one is \{2, 3, 4\}. 
  * A maximum almost-3-uniform set is any pair of vertices on distance 3. 
  * Any single vertex is an almost-k-uniform set for k ≥ 1. 



In the second sample there is an almost-2-uniform set of size 4, and that is \{2, 3, 5, 6\}.

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