TheForces Round #20 (7-Problems-Forces)
A. Tuples
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ tuples $$$(a_i,b_i)(1 \leq a_i \leq 10^8,b_i=-1,1)$$$.

You can do the following operation:

  • Choose an integer $$$k(1\leq k \leq n)$$$;

  • Then choose $$$k$$$ different indexes $$$i_1,i_2,...,i_k$$$.

Your score is defined as $$$(a_{i_1}+a_{i_2}+...a_{i_k})(b_{i_1}+b_{i_2}+...b_{i_k})$$$.

Find the maximum score you can get.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of $$$3$$$ lines of input.

The first line contains an integer $$$n(1 \leq n \leq 2*10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_{n}(1\leq a_i \leq 10^8)$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,...,b_{n}(b_i=-1,1)$$$.

The sum of $$$n$$$ will not exceed $$$2*10^5$$$.

Example
Input
3
5
1 1 1 3 3
1 1 1 -1 -1
3
1 2 3
1 1 1
3
2 1 3
-1 -1 -1
Output
12
18
-1
Note

Test case $$$1$$$:

Choose $$$k=4$$$ and $$$i_1=1,i_2=2,i_3=3,i_4=4$$$.

Test case $$$2$$$:

Choose $$$k=3$$$ and $$$i_1=1,i_2=2,i_3=3$$$.

Test case $$$3$$$:

Choose $$$k=1$$$ and $$$i_1=2$$$.

B. 2-set Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two multiset $$$s,t$$$ of size $$$n$$$.

You can do the following operation:

  • Choose two elements $$$x,y$$$ which satisfy $$$x∈s,y∈t,$$$ and $$$x≠y$$$;
  • Remove $$$x$$$ from $$$s$$$ and remove $$$y$$$ from $$$t$$$.

Determine if you can make $$$s$$$ and $$$t$$$ both empty sets through several operations.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test cases contains three lines.

The first line contains an integer $$$n(1 \leq n \leq 2*10^5)$$$.

The second line contains $$$n$$$ integers $$$x_1,x_2,...,x_n(1 \leq x_i \leq 2n)$$$,denoting the integers in $$$s$$$.

The third line contains $$$n$$$ integers $$$y_1,y_2,...,y_n(1 \leq y_i \leq 2n)$$$,denoting the integers in $$$t$$$.

The sum of $$$n$$$ over all test cases will not exceed $$$2*10^5$$$.

Output

For each test case,output on a new line — if you can make $$$s$$$ and $$$t$$$ both empty sets through several operations,output $$$YES$$$.Otherwise,output $$$NO$$$.

Example
Input
2
3
1 1 2
3 3 2
3
1 1 1
1 1 1
Output
YES
NO
Note

Test case $$$1$$$:

Initially,$$$s=\{1,1,2\},t=\{3,3,2\}$$$.

Operation $$$1$$$:Remove $$$1$$$ from $$$s$$$ and remove $$$3$$$ from $$$t$$$.Now $$$s=\{1,2\},t=\{3,2\}$$$.

Operation $$$2$$$:Remove $$$1$$$ from $$$s$$$ and remove $$$2$$$ from $$$t$$$.Now $$$s=\{2\},t=\{3\}$$$.

Operation $$$3$$$:Remove $$$2$$$ from $$$s$$$ and remove $$$3$$$ from $$$t$$$.Now $$$s$$$ and $$$t$$$ are both empty sets.

Test case $$$2$$$:

You can not make $$$s$$$ and $$$t$$$ both empty sets through several operations.

C. Extended Average
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

If the length of a sequence $$$s$$$ is not less than $$$3$$$,we call $$$s$$$ a valid sequence.

For a valid sequence $$$s$$$,we define the extended average of $$$s$$$ as the average of the remaining numbers after removing one of the maximum value and one of the minimum value in $$$s$$$.

For example,$$$s=\{1,2,1,3,5,3\}$$$,the extended average of $$$s$$$ is $$$\frac{(1+2+3+3)}{4}=2.25$$$.

You're given a sequence $$$a$$$ of size $$$n$$$ and an integer $$$x$$$.Your task is to count the number of valid subsequence $$$b$$$ of $$$a$$$,that the extended average of $$$b$$$ is equal to $$$x$$$.

Since the answer may be very large,output it modulo $$$10^9+7$$$.

Input

The first line of contains two integers $$$n,x(1 \leq n,x \leq 100)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1 \leq a_i \leq 100)$$$.

Output

Output an integer — the number of valid subsequence $$$b$$$ of $$$a$$$,that the extended average of $$$b$$$ is equal to $$$x$$$(modulo $$$10^9+7$$$).

Examples
Input
5 3
5 4 3 2 1
Output
6
Input
6 6
6 6 6 6 6 6
Output
42
Input
16 8
15 3 15 16 5 13 16 13 15 6 14 6 1 3 11 14
Output
689
Note

Test case $$$1$$$:

The following are all subsequences meet the conditions:

$$$\{a_1,a_2,a_3,a_4,a_5\}$$$,$$$\{a_1,a_2,a_4,a_5\}$$$,$$$\{a_1,a_3,a_4\}$$$,$$$\{a_1,a_3,a_5\}$$$,$$$\{a_2,a_3,a_4\}$$$,$$$\{a_2,a_3,a_5\}$$$.

Test case $$$2$$$:

All subsequence with a length of no less than $$$3$$$ meet the conditions.

D. Array Counting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two integers $$$n,m$$$.

Count the number of different arrays $$$a$$$ of size $$$n$$$ satisfy:

  • All $$$a_i(1\leq i \leq n)$$$ are positive integers;

  • $$$\Sigma^{n}_{i=1}a_i=m$$$;

  • Take $$$a_1,a_2,...,a_n$$$ as the length of $$$n$$$ edges,the $$$n$$$ edges can form an $$$n$$$-sided shape.

Since the answer may be very large,output the answer modulo $$$10^9+7$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

The only line of each test case contains two integers $$$n,m(3 \leq n \leq m \leq 10^6)$$$.

Output

For each test case,output on a new line — the number of different arrays satisfy the conditions above (modulo $$$10^9+7$$$).

Example
Input
5
3 3
3 4
3 5
500000 1000000
900000 1000000
Output
1
0
3
998348142
469853029
Note

Test case $$$1$$$:

There's only one array $$$\{1,1,1\}$$$ satisfying the conditions above.

Test case $$$2$$$:

No array satisfies the conditions above.

Test case $$$3$$$:

There're $$$3$$$ arrays $$$\{1,2,2\},\{2,1,2\},\{2,2,1\}$$$ satisfying the conditions above.

E. The Boss Arena
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are inside a boss arena. The arena consists of tiles numbered from $$$1$$$ to $$$n$$$. You spawned at tile $$$s$$$ and your goal is to survive this boss for $$$m$$$ seconds, but there is a catch.

For each second, the boss will shoot a lazer that hit exactly one segment of the arena. If you stand inside said segment when the boss shoots the lazer, you lose the game. More formally, at the $$$i$$$-th second, the boss will shoot a lazer that hit the segment $$$[l_i,r_i]$$$ where $$$1 \leq l_i \leq r_i \leq n$$$. If you currently stand at tile $$$q$$$ where $$$l_i \leq q \leq r_i$$$ when the attack happens, you lose. Of course, you do not want that.

Luckily, you know the attack pattern of the boss for each second. Moreover, you can do a move before each second to avoid the incoming attack. However, it will cost some energy if used. More exactly, before the $$$i$$$-th attack, you can do one of these moves:

  • Do nothing. $$$0$$$ energy will be drained.
  • Instantly teleport $$$k$$$ tiles to the left or to the right $$$(1 \leq k \lt n)$$$. More formally, let $$$j$$$ be the tile you currently stand at. When you use this move, you can either teleport to tile $$$j-k$$$ (if $$$j-k \geq 1$$$) or tile $$$j+k$$$ (if $$$j+k \leq n$$$). $$$k$$$ energy will be drained.

If your energy goes below $$$0$$$, you will also lose. So, you need to stockpile on the energy count. However, grinding energy is very costly. So, calculate the minimum energy needed to survive the boss.

Input

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

The first line of each test case contains three integers $$$n,m,s$$$ $$$(2 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5, 1 \leq s \leq n)$$$ — the number of tiles on the arena, the number of seconds you need to survive, and your starting place.

For the next $$$m$$$ lines in each test case, each line consists of two integers $$$l_i,r_i$$$ $$$(1 \leq l_i \leq r_i \leq n, r_i-l_i+1 \lt n)$$$ — the lazer range at the $$$i$$$-th second.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

Output a single integer, which is the minimum energy needed to survive. It is guaranteed that with the given constraints, you can always survive the boss.

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

For the first test case, this is one of the only optimal movement:

  1. Before the first attack, move from tile $$$4$$$ to tile $$$2$$$.
  2. Before the second attack, move from tile $$$2$$$ to tile $$$1$$$.
  3. Before the third attack, do nothing.
Minimum total energy needed is $$$2+1+0=3$$$. It is impossible to spend less than $$$3$$$ energy without getting hit by the lazer.

For the third test case, it is optimal to keep doing nothing.

F. Happy Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an operation that changes an integer to the sum of the square of all its digits. This operation can be applied to a positive integer as many times as you like.

If a number can become $$$1$$$ after any amount of operations (possibly zero), it is said to be a happy number. A happy number, for instance, is $$$13$$$, which becomes $$$10(1^2 + 3^2 = 10)$$$ after one operation and becomes $$$1(1^2 + 0^2 = 1)$$$ after one more operation. However, $$$2, 3$$$, and $$$4$$$ are not happy numbers.

You are given $$$t$$$ closed intervals, each represented by two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \leq i \leq t)$$$. For each interval, please determine the number of happy numbers in the interval.

Formally, for each query $$$i$$$, please compute

$$$$$$\sum_{x=l_i}^{r_i}f(x)$$$$$$

where $$$f(x)=1$$$ if $$$x$$$ is a happy number and $$$f(x)=0$$$ if $$$x$$$ is not a happy number.

Since the answers can be very large, please print them modulo $$$10^9+7$$$.

Input

The first line contains one integer $$$t$$$ $$$(1 \leq t \leq 100)$$$ — the number of test cases.

The only line of each test case contains two integers $$$l_i, r_i$$$ $$$(1 \leq l_i \leq r_i \leq 10^{200})$$$.

It is guaranteed that the sum of the lengths of all inputted integers does not exceed $$$10^3$$$.

Output

Print $$$t$$$ lines, each containing one integer — the number of happy numbers in the given closed interval, modulo $$$10^9+7$$$.

Example
Input
4
7 7
5 10
1 1000
1 999999
Output
1
2
143
143070
Note

In the first range, $$$7$$$ is a happy number because $$$7^2=49$$$; $$$4^2+9^2=97$$$; $$$9^2+7^2=130$$$; $$$1^2+3^2+0^2=10$$$; $$$1^2+0^2=1$$$.

In the second range, the two happy numbers are $$$7, 10$$$.

G. Angel's Salad
time limit per test
10 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a sequence $$$a$$$ of length $$$n$$$ and $$$m$$$ intervals $$$[l_i,r_i]$$$. Initially,$$$a_i=0$$$ for all $$$1 \leq i \leq n$$$.

Here is a sequence $$$b$$$, generated in such a way that all the intervals are expanded into numbers and then put together consecutively.

Formally,$$$b=[a[l_1,...,r_1],a[l_2,...,r_2],...,a[l_m,...,r_m]]$$$.

You have $$$q$$$ queries.Each query is one of the following two types:

1 l r v It means adding $$$v$$$ to all values of $$$a_i$$$ that $$$l\le i\le r$$$($$$1\le l\le r\le n$$$,$$$0\le v\le10^3$$$).

2 l r It means outputing the value of $$$\sum\limits_{i=l}^r b_i$$$( $$$1\le l\le r\le |b|$$$).

Input

The first line has $$$3$$$ integers $$$n$$$, $$$m$$$, $$$q$$$($$$1\le n,m,q\le10^5$$$).

Next $$$m$$$ lines, $$$2$$$ integers per line $$$l_i,r_i(1\leq l_i \leq r_i \leq n)$$$.

Next $$$q$$$ line, $$$3$$$ or $$$4$$$ integers per line,denoting query $$$1$$$ or $$$2$$$.

Output

Only one line,for each query of type $$$2$$$, outputs the value(separated by a space).

Example
Input
4 2 4
1 3
2 4
1 1 2 1
2 2 5
1 2 4 2
2 1 6
Output
2 13
Note

Query $$$1$$$:

Add $$$1$$$ to $$$a_1,a_2$$$.Now $$$a=[1,1,0,0]$$$,$$$b=[1,1,0,1,0,0]$$$.

Query $$$2$$$:

$$$\sum\limits_{i=2}^5 b_i=1+0+1+0=2$$$.

Query $$$3$$$:

Add $$$2$$$ to $$$a_2,a_3,a_4$$$.Now $$$a=[1,3,2,2]$$$,$$$b=[1,3,2,3,2,2]$$$.

Query $$$4$$$:

$$$\sum\limits_{i=1}^6 b_i=1+3+2+3+2+2=13$$$.