TheForces Round #36 (Starters-Forces)
A. Sum Fun
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"Judge things by their sum."
—Wise Man

You are given two integers $$$n$$$, $$$m$$$. Please determine if there exists a positive integer $$$s$$$ such that the following conditions are true:

  • It does not contain the digit $$$0$$$;‎‎ ‎
  • It consists of $$$n$$$ digits;
  • The sum of its digits is exactly $$$m$$$;
  • It is a palindrome.$$$^\dagger$$$

$$$^\dagger$$$ A positive integer $$$a$$$ is called a palindrome when it reads the same when the order of digits is reversed.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^8$$$) — the number of digits and the sum of digits.

Output

For each test case, if there exists a valid integer $$$s$$$, print "YES"; otherwise, print "NO".

You can output the answer in any case (For example, the strings "yEs", "yes", "Yes", and "YeS" will be recognized as positive responses).

Example
Input
7
7 10
8 10
7 15
10 20
90 100
10 78
2 5
Output
YES
YES
YES
YES
YES
YES
NO
Note

In the first test case, $$$2\,112\,112$$$ satisfies all four conditions:

  • $$$2\,112\,112$$$ does not contain the digit $$$0$$$.
  • $$$2\,112\,112$$$ consists of $$$7$$$ digits, and the sum of digits is $$$10$$$.
  • $$$2\,112\,112$$$ is a palindrome.

Therefore, $$$2\,112\,112$$$ can be an answer.

In the second test case, it can be shown that there is no integer $$$s$$$ which satisfies all the conditions.

In the fourth test case, $$$1\,232\,222\,321$$$ can be an answer.

B. Interviews
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$x$$$ interviewers numbered from $$$1$$$ to $$$x$$$. Each of the interviewers can conduct at most $$$y$$$ interviews per day. An interview consists of $$$z$$$ different interviewers interviewing one participant.

Calculate the maximum number of participants that can be interviewed in a day (in other words, interviews that can be conducted in a day) and output any one of the schemes.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

For each test case:

  • The first line contains three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le x, y, z \le 10$$$).
Output

For each test case,

  • In the first line output a single integer $$$k$$$  — the number of participants that can be interviewed in a day;
  • The next $$$k$$$ lines, for each line, output $$$z$$$ different space-separated integers, representing the numbers of the interviewers conducting the interviews;
  • The occurrence of each number should not exceed $$$y$$$.

If there are multiple schemes, you can output any.

Example
Input
3
3 1 2
3 2 2
4 10 5
Output
1
1 2
3
1 2
2 3
1 3
0

C. Sigma Problem (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference is that $$$q=1$$$, $$$l=1$$$ and $$$r=n$$$ in this version.

You are given an array $$$a$$$ of length $$$n$$$. Note $$$$$$s(l,r) = \sum_{i=l}^{r} \sum_{j=i}^{r} \prod_{k=i}^j a_k$$$$$$

where $$$\prod_{k=i}^j a_j$$$ is defined as the product of all elements in the array $$$a$$$ from index $$$i$$$ to $$$j$$$, i.e. $$$(a_i \times a_{i+1} \times ... \times a_j)$$$.

You need to handle $$$q$$$ queries. Each query gives two numbers $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le n)$$$, and you should output $$$s(l,r)$$$.

For each query, you need to output the value modulo $$$10^9+7$$$.

Input

The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^5)$$$.

For each test case:

  • The first line contains a single integer $$$n$$$, $$$q$$$ $$$(2 \leq n \leq 10^{6}$$$, $$$q=1)$$$, the length of the array;
  • The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$;
  • For the next $$$q$$$ lines, each line contains two integers $$$l$$$, $$$r$$$ $$$(l=1$$$, $$$r=n)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{6}$$$.

Output

For each query, output ina new line  — the value of $$$s(l,r)$$$ modulo $$$10^9+7$$$.

Example
Input
2
3 1
2 4 3
1 3
4 1
1000000000 1000000000 1000000000 1000000000
1 4
Output
53
1834
Note

In the first test case, $$$a=[2,4,3]$$$ and you need to calculate $$$s(1,3)$$$ in the first query.

For $$$i = 1$$$: $$$$$$ \begin{align*} j = 1: & \quad \prod_{k=1}^{1} a_k = 2 \\ j = 2: & \quad \prod_{k=1}^{2} a_k = 2 \times 4 = 8 \\ j = 3: & \quad \prod_{k=1}^{3} a_k = 2 \times 4 \times 3 = 24 \\ \end{align*} $$$$$$

For $$$i = 2$$$: $$$$$$ \begin{align*} j = 2: & \quad \prod_{k=2}^{2} a_k = 4 \\ j = 3: & \quad \prod_{k=2}^{3} a_k = 4 \times 3 = 12 \\ \end{align*} $$$$$$

For $$$i = 3$$$: $$$$$$ \begin{align*} j = 3: & \quad \prod_{k=3}^{3} a_k = 3 \\ \end{align*} $$$$$$

Thus, $$$s(1,3) = 2+8+34+4+12+3 = 53$$$.

D. YEET!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two integers $$$n$$$ and $$$m$$$, find any permutation of length $$$n$$$ such that the following conditions hold. $$$$$$ \begin{cases} \gcd(p_i,p_{i+1}) \neq m \ (1 \le i \le n-1) \\ (p_i+p_{i+1}) \mod m \neq 0 \ (1 \le i \le n-1) \\ \end{cases} $$$$$$

Input

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

For each test case:

  • The only line contains two integers $$$n,m$$$ ($$$2 \le n,m \le 5 \cdot 10^5$$$).

It's guaranteed that the sum of $$$n+m$$$ overall test cases doesn't exceed $$$ 10^6$$$.

Output

For each test case, if there is no such permutation, print $$$-1$$$. Otherwise, print any valid permutation that satisfies the condition.

Example
Input
3
4 4
5 7
9 7
Output
1 2 3 4
1 3 2 4 5
1 8 3 2 9 4 5 6 7

E. Sigma Problem (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference is that $$$1\le q \le 2 \cdot 10^6$$$, $$$1 \le l \le r \le n$$$ in this version.

You are given an array $$$a$$$ of length $$$n$$$. Note $$$$$$s(l,r) = \sum_{i=l}^{r} \sum_{j=i}^{r} \prod_{k=i}^j a_k$$$$$$

where $$$\prod_{k=i}^j a_j$$$ is defined as the product of all elements in the array $$$a$$$ from index $$$i$$$ to $$$j$$$, i.e. $$$(a_i \times a_{i+1} \times ... \times a_j)$$$.

You need to handle $$$q$$$ queries. Each query gives two numbers $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le n)$$$, and you should output $$$s(l,r)$$$.

For each query, you need to output the value modulo $$$10^9+7$$$.

Input

The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^5)$$$.

For each test case:

  • The first line contains a single integer $$$n$$$, $$$q$$$ $$$(2 \leq n \leq 10^{6}$$$, $$$1\le q \le 2 \cdot 10^6)$$$;
  • The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$;
  • For the next $$$q$$$ lines, each line contains two integers $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le n)$$$

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^6$$$.

Output

For each query, output ina new line  — the value of $$$s(l,r)$$$ modulo $$$10^9+7$$$.

Example
Input
2
3 1
2 4 3
1 3
4 3
1000000000 1000000000 1000000000 1000000000
1 4
2 3
4 4
Output
53
1834
35
1000000000
Note

In the first test case, $$$a=[2,4,3]$$$ and you need to calculate $$$s(1,3)$$$ in the first query.

For $$$i = 1$$$: $$$$$$ \begin{align*} j = 1: & \quad \prod_{k=1}^{1} a_k = 2 \\ j = 2: & \quad \prod_{k=1}^{2} a_k = 2 \times 4 = 8 \\ j = 3: & \quad \prod_{k=1}^{3} a_k = 2 \times 4 \times 3 = 24 \\ \end{align*} $$$$$$

For $$$i = 2$$$: $$$$$$ \begin{align*} j = 2: & \quad \prod_{k=2}^{2} a_k = 4 \\ j = 3: & \quad \prod_{k=2}^{3} a_k = 4 \times 3 = 12 \\ \end{align*} $$$$$$

For $$$i = 3$$$: $$$$$$ \begin{align*} j = 3: & \quad \prod_{k=3}^{3} a_k = 3 \\ \end{align*} $$$$$$

Thus, $$$s(1,3) = 2+8+34+4+12+3 = 53$$$.

F. Ranking Random Pick
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For an array $$$b$$$ of length $$$l$$$, a ranking random pick is defined as follows: from the non-decreasing sorted version of array $$$b$$$ (denoted as array $$$c$$$), exactly one element is selected, where the probability of selecting $$$c_i$$$ is given by $$$\frac{i}{1 + 2 + \dots + l}$$$.

Alice and Bob have an array $$$a$$$ of length $$$n$$$ and a fair coin. Initially, Alice's score is $$$0$$$.

If array $$$a$$$ is non-empty, the coin is flipped:

  • If the coin shows heads, Bob performs a ranking random pick from $$$a$$$ and removes the selected element from $$$a$$$.
  • If the coin shows tails, Alice performs a ranking random pick from $$$a$$$, adds the value of the selected element to her score, and removes all elements from $$$a$$$.

Calculate the expected value of Alice's score. Output the answer modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 400$$$). The description of the test cases follows.

  • The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$);
  • The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, print a single integer — the answer to the problem modulo $$$998\,244\,353$$$.

Example
Input
3
1
2
2
3 5
5
1000000000 999999999 999999999 1000000000 999999998
Output
1
582309209
588585275
Note

In the first case, Alice has $$$\frac{1}{2}$$$ probability of getting a score of $$$2$$$, and $$$\frac{1}{2}$$$ probability of getting a score of $$$0$$$, so the expected score for Alice is $$$\frac{1}{2} \times 2+\frac{1}{2}\times 0=1$$$.

In the second case, Alice's expected score is $$$\frac{1}{2}\times\frac{1}{3} \times 3+\frac{1}{2}\times\frac{2}{3} \times 5+\frac{1}{2}\times\frac{1}{3} \times \frac{1}{2}\times5+\frac{1}{2}\times\frac{2}{3} \times \frac{1}{2}\times3=\frac{37}{12}$$$.

The game tree for the second case.

G. Timosh and Set
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Assume there is a positive integer $$$x$$$ and an array $$$a$$$ of size $$$n$$$. In one operation, you can choose any element $$$a_i$$$ $$$(1 \le i \le n)$$$ from the array, then set $$$x:=x- x\mod a_i$$$.

Note $$$f(x)$$$ as the minimum number of operations to make $$$x=0$$$. For a given array $$$a$$$ of size $$$n$$$ and a given integer $$$m$$$, calculate $$$\sum_{i=1}^{m}f(i)$$$.

Input data guarantees that for all $$$x=1,2,\ldots,m$$$, $$$x$$$ can always be reduced to $$$0$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ – the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ $$$(2 \le n \le 2 \cdot 10^5 , 1 \le m \le 10^7)$$$ – the length of set $$$a$$$ and integer $$$m$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le 10^7)$$$.

Input data guarantees that for all $$$x=1,2,\ldots,m$$$, $$$x$$$ can always be reduced to $$$0$$$.

It's guaranteed that the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

It's guaranteed that the sum of $$$m$$$ doesn't exceed $$$10^7$$$.

Output

For each test case, output an integer in a new line  — $$$\sum_{i=1}^{m}f(i)$$$.

Example
Input
2
4 6
1 2 3 4
2 7
2 5
Output
10
12
Note

In the first test case,

  • $$$f(1)=f(2)=f(3)=1$$$;
  • $$$f(4)=f(5)=2$$$;
  • $$$f(6)=3$$$.

So the answer is $$$1+1+1+2+2+3=10$$$.