vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Blog Photo

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
One popular blog site edits the uploaded photos like this. It cuts a rectangular area out of them so that the ratio of height to width (i.e. the *height*<=/<=*width* quotient) can vary from 0.8 to 1.25 inclusively. Besides, at least one side of the cut area should have a size, equal to some power of number 2 (2*x* for some integer *x*). If those rules don't indicate the size of the cut are clearly, then the way with which the cut part possesses the largest area is chosen. Of course, both sides of the cut area should be integer. If there are several answers to this problem, you should choose the answer with the maximal height.

Input Specification:
The first line contains a pair of integers *h* and *w* (1<=≤<=*h*,<=*w*<=≤<=109) which are the height and width of the uploaded photo in pixels.

Output Specification:
Print two integers which are the height and width of the cut area.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The determinant of a matrix 2 × 2 is defined as follows:$\operatorname{det} \left(\begin{array}{ll}{a} & {b} \\{c} & {d} \end{array} \right) = a d - b c$

A matrix is called degenerate if its determinant is equal to zero. 

The norm ||A|| of a matrix A is defined as a maximum of absolute values of its elements.

You are given a matrix $A = \left(\begin{array}{ll}{a} & {b} \\{c} & {d} \end{array} \right)$. Consider any degenerate matrix B such that norm ||A - B|| is minimum possible. Determine ||A - B||.


-----Input-----

The first line contains two integers a and b (|a|, |b| ≤ 10^9), the elements of the first row of matrix A. 

The second line contains two integers c and d (|c|, |d| ≤ 10^9) the elements of the second row of matrix A.


-----Output-----

Output a single real number, the minimum possible value of ||A - B||. Your answer is considered to be correct if its absolute or relative error does not exceed 10^{ - 9}.


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

Output
0.2000000000

Input
1 0
0 1

Output
0.5000000000



-----Note-----

In the first sample matrix B is $\left(\begin{array}{ll}{1.2} & {1.8} \\{2.8} & {4.2} \end{array} \right)$

In the second sample matrix B is $\left(\begin{array}{ll}{0.5} & {0.5} \\{0.5} & {0.5} \end{array} \right)$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tavas lives in Tavaspolis. Tavaspolis has n cities numbered from 1 to n connected by n - 1 bidirectional roads. There exists a path between any two cities. Also each road has a length.

<image>

Tavas' favorite strings are binary strings (they contain only 0 and 1). For any binary string like s = s1s2... sk, T(s) is its Goodness. T(s) can be calculated as follows:

Consider there are exactly m blocks of 1s in this string (a block of 1s in s is a maximal consecutive substring of s that only contains 1) with lengths x1, x2, ..., xm.

Define <image> where f is a given sequence (if m = 0, then T(s) = 0).

Tavas loves queries. He asks you to answer q queries. In each query he gives you numbers v, u, l and you should print following number:

Consider the roads on the path from city v to city u: e1, e2, ..., ex.

Build the binary string b of length x such that: bi = 1 if and only if l ≤ w(ei) where w(e) is the length of road e.

You should print T(b) for this query.

Input

The first line of input contains integers n and q (2 ≤ n ≤ 105 and 1 ≤ q ≤ 105).

The next line contains n - 1 space separated integers f1, f2, ..., fn - 1 (|fi| ≤ 1000).

The next n - 1 lines contain the details of the roads. Each line contains integers v, u and w and it means that there's a road between cities v and u of length w (1 ≤ v, u ≤ n and 1 ≤ w ≤ 109).

The next q lines contain the details of the queries. Each line contains integers v, u, l (1 ≤ v, u ≤ n, v ≠ u and 1 ≤ l ≤ 109).

Output

Print the answer of each query in a single line.

Examples

Input

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


Output

10
10
0


Input

6 6
-5 0 0 2 10
1 2 1
2 3 2
3 4 5
4 5 1
5 6 5
1 6 1
1 6 2
1 6 5
3 6 5
4 6 4
1 4 2


Output

10
-5
-10
-10
-5
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a of n integers. Define the cost of some array t as follows:

$$$cost(t) = ∑_{x ∈ set(t) } last(x) - first(x),$$$ 

where set(t) is the set of all values in t without repetitions, first(x), and last(x) are the indices of the first and last occurrence of x in t, respectively. In other words, we compute the distance between the first and last occurrences for each distinct element and sum them up.

You need to split the array a into k consecutive segments such that each element of a belongs to exactly one segment and the sum of the cost of individual segments is minimum.

Input

The first line contains two integers n, k (1 ≤ n ≤ 35 000, 1 ≤ k ≤ min(n,100)).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n).

Output

Output the minimum sum of the cost of individual segments.

Examples

Input


7 2
1 6 6 4 6 6 6


Output


3


Input


7 4
5 5 5 5 2 3 3


Output


1

Note

In the first example, we can divide the array into [1,6,6,4] and [6,6,6]. Cost of [1,6,6,4] will be (1-1) + (3 - 2) + (4-4) = 1 and cost of [6,6,6] will be 3-1 = 2. Total cost would be 1 + 2 = 3.

In the second example, divide the array into [5,5],[5],[5,2,3] and [3]. Total Cost would be 1 + 0 + 0 + 0 = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Surely you have seen insane videos by South Korean rapper PSY, such as "Gangnam Style", "Gentleman" and "Daddy". You might also hear that PSY has been recording video "Oppa Funcan Style" two years ago (unfortunately we couldn't find it on the internet). We will remind you what this hit looked like (you can find original description [here](http://acm.timus.ru/problem.aspx?space=1&num=2107&locale=en)):

On the ground there are n platforms, which are numbered with integers from 1 to n, on i-th platform there is a dancer with number i. Further, every second all the dancers standing on the platform with number i jump to the platform with the number f(i). The moving rule f is selected in advance and is not changed throughout the clip.

The duration of the clip was k seconds and the rule f was chosen in such a way that after k seconds all dancers were in their initial positions (i.e. the i-th dancer stood on the platform with the number i). That allowed to loop the clip and collect even more likes.

PSY knows that enhanced versions of old artworks become more and more popular every day. So he decided to release a remastered-version of his video.

In his case "enhanced version" means even more insanity, so the number of platforms can be up to 10^{18}! But the video director said that if some dancer stays on the same platform all the time, then the viewer will get bored and will turn off the video immediately. Therefore, for all x from 1 to n f(x) ≠ x must hold.

Big part of classic video's success was in that looping, so in the remastered version all dancers should return to their initial positions in the end of the clip as well.

PSY hasn't decided on the exact number of platforms and video duration yet, so he asks you to check if there is a good rule f for different options.

Input

In the first line of input there is one integer t (1 ≤ t ≤ 10^{4}) — the number of options for n and k to check.

In the next t lines the options are given: each option is described with two integers n and k (1 ≤ n ≤ 10^{18}, 1 ≤ k ≤ 10^{15}) — the number of dancers and the duration in seconds.

It is guaranteed that the number of different values of k in one test is not greater than 50.

Output

Print t lines. If the i-th option of the video is feasible, print "YES" (without quotes) in i-th line, otherwise print "NO" (without quotes).

Example

Input

3
7 7
3 8
5 6


Output

YES
NO
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Function Descriptions=====
dot

The dot tool returns the dot product of two arrays.

import numpy

A = numpy.array([ 1, 2 ])
B = numpy.array([ 3, 4 ])

print numpy.dot(A, B)       #Output : 11

cross

The cross tool returns the cross product of two arrays.

import numpy

A = numpy.array([ 1, 2 ])
B = numpy.array([ 3, 4 ])

print numpy.cross(A, B)     #Output : -2

=====Problem Statement=====
You are given two arrays A and B. Both have dimensions of NXN.
Your task is to compute their matrix product.

=====Input Format=====
The first line contains the integer N.
The next N lines contains N space separated integers of array A.
The following N lines contains N space separated integers of array B.

=====Output Format=====
Print the matrix multiplication of A and B.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n children, who study at the school №41. It is well-known that they are good mathematicians. Once at a break, they arranged a challenge for themselves. All children arranged in a row and turned heads either to the left or to the right.

Children can do the following: in one second several pairs of neighboring children who are looking at each other can simultaneously turn the head in the opposite direction. For instance, the one who was looking at the right neighbor turns left and vice versa for the second child. Moreover, every second at least one pair of neighboring children performs such action. They are going to finish when there is no pair of neighboring children who are looking at each other. 

You are given the number n, the initial arrangement of children and the number k. You have to find a way for the children to act if they want to finish the process in exactly k seconds. More formally, for each of the k moves, you need to output the numbers of the children who turn left during this move.

For instance, for the configuration shown below and k = 2 children can do the following steps: 

<image> At the beginning, two pairs make move: (1, 2) and (3, 4). After that, we receive the following configuration:  <image> At the second move pair (2, 3) makes the move. The final configuration is reached. Good job.  <image>

It is guaranteed that if the solution exists, it takes not more than n^2 "headturns".

Input

The first line of input contains two integers n and k (2 ≤ n ≤ 3000, 1 ≤ k ≤ 3000000) — the number of children and required number of moves.

The next line contains a string of length n and consists only of characters L and R, where L means that the child looks to the left and R means that the child looks to the right. 

Output

If there is no solution, print a single line with number -1.

Otherwise, output k lines. Each line has to start with a number n_i (1≤ n_i ≤ n/2) — the number of pairs of children, who turn at this move. After that print n_i distinct integers — the numbers of the children who will turn left during this move. 

After performing all "headturns", there can't be a pair of two neighboring children looking at each other.

If there are many solutions, print any of them.

Examples

Input


2 1
RL


Output


1 1 


Input


2 1
LR


Output


-1

Input


4 2
RLRL


Output


2 1 3 
1 2

Note

The first sample contains a pair of children who look at each other. After one move, they can finish the process.

In the second sample, children can't make any move. As a result, they can't end in k>0 moves.

The third configuration is described in the statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bill Total Value

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasily exited from a store and now he wants to recheck the total price of all purchases in his bill. The bill is a string in which the names of the purchases and their prices are printed in a row without any spaces. Check has the format "*name*1*price*1*name*2*price*2...*name**n**price**n*", where *name**i* (name of the *i*-th purchase) is a non-empty string of length not more than 10, consisting of lowercase English letters, and *price**i* (the price of the *i*-th purchase) is a non-empty string, consisting of digits and dots (decimal points). It is possible that purchases with equal names have different prices.

The price of each purchase is written in the following format. If the price is an integer number of dollars then cents are not written.

Otherwise, after the number of dollars a dot (decimal point) is written followed by cents in a two-digit format (if number of cents is between 1 and 9 inclusively, there is a leading zero).

Also, every three digits (from less significant to the most) in dollars are separated by dot (decimal point). No extra leading zeroes are allowed. The price always starts with a digit and ends with a digit.

For example:
 -  "234", "1.544", "149.431.10", "0.99" and "123.05" are valid prices, -  ".333", "3.33.11", "12.00", ".33", "0.1234" and "1.2" are not valid. 
Write a program that will find the total price of all purchases in the given bill.

Input Specification:
The only line of the input contains a non-empty string *s* with length not greater than 1000 — the content of the bill.

It is guaranteed that the bill meets the format described above. It is guaranteed that each price in the bill is not less than one cent and not greater than 106 dollars.

Output Specification:
Print the total price exactly in the same format as prices given in the input.

Demo Input:
['chipsy48.32televizor12.390\n', 'a1b2c3.38\n', 'aa0.01t0.03\n']

Demo Output:
['12.438.32\n', '6.38\n', '0.04\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n segments on the Ox axis. The i-th segment is given as a pair l_i, r_i, where l_i is the position of the left end of the i-th segment and r_i is the position of the right end of the i-th segment. Segments may intersect, overlap, or even coincide. A segment is a set of numbers (including floating-point numbers) lying between the segment ends or coinciding with them. Formally, the segment [l, r]=\\{x~|~x ∈ \Bbb{R},~l ≤ x ≤ r\}.

Let the union of segments be the set of all axis points covered by the set of segments. Let's call a subset of the given segments good if its union equals the union of all n segments.

Your task is to calculate the number of good subsets of the given n segments. Since the answer may be very large, print it modulo 998244353.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of segments.

The next n lines contain segments. The i-th segment is given as a pair l_i, r_i (1 ≤ l_i ≤ r_i ≤ 10^9), where l_i is the left border of the segment and r_i is the right border of the segment. Segments may intersect, overlap, or even coincide.

Output

Print the number of good subsets of the given set of segments. Since the answer may be very large, print it modulo 998244353.

Examples

Input


3
1 1
2 6
1 6


Output


4


Input


2
3 4
2 5


Output


2


Input


4
1 2
5 5
2 3
1 3


Output


5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Simple Cycles Edges

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an undirected graph, consisting of $n$ vertices and $m$ edges. The graph does not necessarily connected. Guaranteed, that the graph does not contain multiple edges (more than one edges between a pair of vertices) or loops (edges from a vertex to itself).

A cycle in a graph is called a simple, if it contains each own vertex exactly once. So simple cycle doesn't allow to visit a vertex more than once in a cycle.

Determine the edges, which belong to exactly on one simple cycle.

Input Specification:
The first line contain two integers $n$ and $m$ $(1 \le n \le 100\,000$, $0 \le m \le \min(n \cdot (n - 1) / 2, 100\,000))$ — the number of vertices and the number of edges.

Each of the following $m$ lines contain two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) — the description of the edges.

Output Specification:
In the first line print the number of edges, which belong to exactly one simple cycle.

In the second line print the indices of edges, which belong to exactly one simple cycle, in increasing order. The edges are numbered from one in the same order as they are given in the input.

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

Demo Output:
['3\n1 2 3 \n', '6\n1 2 3 5 6 7 \n', '0\n\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Matthew the physicist studies the quantum electro-dynamics of a silicon-based rectangular microchip. The microchip consists of a very large $N \times M$ grid of electrons. Each electron has either positive (up) or negative (down) spin, denoted by $+$ and $-$ respectively.

Matthew does not know the spin of all the electrons, but he has done $K$ measurements. In the $i$-th measurement, he discovered that the electron at position $(y_ i, x_ i)$ has a given spin $s_ i$. He also knows that in each $2\times 2$ subgrid, there are equally many electrons with positive and negative spin. He wants to know whether he can recover the state of every electron based on his measurements. If not, he would like to know how many possible states are consistent with his measurements. For classified reasons, he wants the answer modulo $10^9 + 7$.

-----Input-----
The first line contain three numbers $N$, $M$ and $K$: the height of the grid, the width of the grid and the number of measurements. The next $K$ lines contain a spin $s_ i$ where $s_ i$ is either $+$ or $-$, and two numbers $1 \leq y_ i \leq N$ and $1 \leq x_ i \leq M$ – the coordinates of the electron. Matthew never did two measurments at the exact same location.

We always have $1 \leq N, M \leq 10^9$ and $0 \leq K \leq 100000$.

-----Output-----
Output the total number of valid states consistent with Matthew’ measurements modulo $10^9 + 7$.

-----Examples-----
Sample Input:
2 4 4
+ 1 1
- 1 2
+ 1 3
- 1 4
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke loves permutations. He is making a permutation of length N.

Since he hates the integer K, his permutation will satisfy the following:

* Let the permutation be a_1, a_2, ..., a_N. For each i = 1,2,...,N, |a_i - i| \neq K.



Among the N! permutations of length N, how many satisfies this condition?

Since the answer may be extremely large, find the answer modulo 924844033(prime).

Constraints

* 2 ≦ N ≦ 2000
* 1 ≦ K ≦ N-1

Input

The input is given from Standard Input in the following format:


N K


Output

Print the answer modulo 924844033.

Examples

Input

3 1


Output

2


Input

4 1


Output

5


Input

4 2


Output

9


Input

4 3


Output

14


Input

425 48


Output

756765083

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: T-shirts from Sponsor

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
One day a well-known sponsor of a well-known contest decided to give every participant of the contest a T-shirt as a present. A natural problem occurred: on the one hand, it is not clear how many T-shirts of what sizes should be ordered, and on the other hand, one doesn't want to order too many T-shirts (and we do not exactly paper the walls with the oversupply). After considerable brain racking and some pre-estimating, the sponsor representatives ordered a certain number of T-shirts of sizes S, M, L, XL and XXL. The T-shirts turned out to bring good luck, that's why on the contest day there built up a line of *K* participants willing to get one. Every contestant is characterized by his/her desired T-shirt size (so it happens that for all the participants it is also one of the sizes S, M, L, XL and XXL). The participants come up to get a T-shirt one by one and try to choose the most suitable one, choosing it like this. If there is still a T-shirt of the optimal size left, that he/she takes it without further ado. Otherwise the contestant would prefer to choose a T-shirt with the size as close to the optimal one as possible (the distance between neighboring sizes is considered equal to one). If the variant of choice is not unique, the contestant will take a T-shirt of a bigger size (in case he/she grows more). For example, for a person whose optimal size is L the preference list looks like this: L, XL, M, XXL, S. Using the data on how many T-shirts of every size had been ordered by the organizers, on the size of contestants in the line determine who got a T-shirt of what size.

Input Specification:
The first line contains five non-negative integers *N**S*,<=*N**M*,<=*N**L*,<=*N**XL*,<=*N**XXL* not exceeding 1000 which represent the number of T-shirts of the corresponding sizes. The second line contains an integer *K* (1<=≤<=*K*<=≤<=1000) which represents the number of participants. The next *K* lines contain the optimal T-shirt sizes for the contestants. The sizes are given in the order in which the participants stand in the line. It is guaranteed that *N**S*<=+<=*N**M*<=+<=*N**L*<=+<=*N**XL*<=+<=*N**XXL*<=≥<=*K*.

Output Specification:
For each contestant, print a line containing the size of the T-shirt he/she got.

Demo Input:
['1 0 2 0 1\n3\nXL\nXXL\nM\n']

Demo Output:
['XXL\nL\nL\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Vitaly was going home late at night and wondering: how many people aren't sleeping at that moment? To estimate, Vitaly decided to look which windows are lit in the house he was passing by at that moment.

Vitaly sees a building of *n* floors and 2·*m* windows on each floor. On each floor there are *m* flats numbered from 1 to *m*, and two consecutive windows correspond to each flat. If we number the windows from 1 to 2·*m* from left to right, then the *j*-th flat of the *i*-th floor has windows 2·*j*<=-<=1 and 2·*j* in the corresponding row of windows (as usual, floors are enumerated from the bottom). Vitaly thinks that people in the flat aren't sleeping at that moment if at least one of the windows corresponding to this flat has lights on.

Given the information about the windows of the given house, your task is to calculate the number of flats where, according to Vitaly, people aren't sleeping.

Input Specification:
The first line of the input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100) — the number of floors in the house and the number of flats on each floor respectively.

Next *n* lines describe the floors from top to bottom and contain 2·*m* characters each. If the *i*-th window of the given floor has lights on, then the *i*-th character of this line is '1', otherwise it is '0'.

Output Specification:
Print a single integer — the number of flats that have lights on in at least one window, that is, the flats where, according to Vitaly, people aren't sleeping.

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

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

Note:
In the first test case the house has two floors, two flats on each floor. That is, in total there are 4 flats. The light isn't on only on the second floor in the left flat. That is, in both rooms of the flat the light is off.

In the second test case the house has one floor and the first floor has three flats. The light is on in the leftmost flat (in both windows) and in the middle flat (in one window). In the right flat the light is off.

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