TheForces Round #14 (Cool-Forces)
A. Dungeon videogame
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a dungeon consisting of $$$n$$$ levels, numbered from $$$1$$$ to $$$n$$$. You are given an array $$$a = a_1, a_{2}, ..., a_{n}$$$, where each element $$$a_{i}$$$ represents the number of points that can be scored at level $$$i$$$.

Initially, your score is $$$0$$$.

You have two available operations at every level from $$$1$$$ to $$$n$$$ :

  • Solve Level : Solve the $$$i_{th}$$$ level, and add $$$a_{i}$$$ points to your score. It is important to note that $$$a_{i}$$$ can be negative.
  • Skip Segment : Skip a contiguous range of levels, from $$$i_{th}$$$ to $$$j_{th}$$$ level, where $$$i \le j \le n$$$, and lose $$$(j - i + 1)$$$ points which equals to the number of levels in the chosen segment.

Note that you are allowed to apply exactly one of the two options above at each level.

Find the maximum possible score you can obtain.

Input

In the first line of the input You'll be given $$$t$$$ the number of testcases.

In the first line of each next $$$t$$$ testcases You'll be given an integer $$$n$$$ which shows the number of levels.

In the second line of each testcase You'll be given an array of length $$$n$$$.

$$$1 \le t \le 10^4$$$.

$$$1 \le n \le 2 \cdot 10^5$$$.

$$$1 \le |a_i| \le 10^9$$$.

It is guaranteed that sum of $$$n$$$ overall testcases does not exceed $$$2 \cdot 10^5$$$.

Output

Print the maximum score you can achieve.

Example
Input
4
5
-1 -1 -1 2 -1
3
5 5 6
2
-1000000000 1
5
-2 -2 3 4 -1
Output
-2
16
0
4

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

You are given an array of positive integers of length $$$n$$$.

You need to find a value $$$x$$$ such that sum of $$$|a_i - x - i|$$$ over all $$$1 \le i \le n$$$ is minimized (This is declared as the $$$summation$$$ of the array).

Now your task is to print the minimum $$$summation$$$.

Input

In the first line of input You'll be given a number $$$n$$$ which shows the length of the array.

In the second line You'll receive an array $$$a$$$ of positive integers.

$$$1 \le n \le 10^5$$$.

$$$1 \le a_i \le 10^9$$$.

Output

Print the minimum $$$summation$$$ possible.

Example
Input
5
2 3 4 6 8
Output
3

C. Prefix Sum Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There's an array of size $$$10^{18}$$$ which every element of the array is $$$1$$$. After each second, Every element of the array becomes the prefix sum of it's position, it means for example at a second the array is $$$a_{1}, a_{2}, a_{3}, ....$$$ in the next second the array becomes $$$a_{1}, a_{1} + a_{2}, a_{1} + a_{2} + a_{3}, ....$$$ . Now your task is to find the $$$n_{th}$$$ element of the array after $$$k$$$ seconds.

Input

In the first line of input, You'll be given a number $$$t$$$ which shows the number of testcases.

In the next $$$t$$$ lines you'll be given two integers $$$n$$$ and $$$k$$$.

$$$1 \le t \le 10^{5}, 1 \le n \le 10^{5}, 1 \le k \le 10^5$$$.

Note that for each testcases the initial array is filled with $$$1$$$.

Output

As the answer can be large print the answer modulo $$$10^9 + 7$$$.

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

Testcase $$$1$$$ :

The array at second $$$0 : 1, 1, 1, 1, 1, 1, ...$$$

The array at second $$$1 : 1, 2, 3, 4, 5, 6, ...$$$

The array at second $$$2 : 1, 3, 6, 10, 15, 21, ...$$$

D. Comic Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A comic number is defined as a positive integer which is divisible by the floor of its cubic root (the third root). Example : $$$68$$$ is divisible by $$$\lfloor \sqrt[3]{68} \rfloor = \lfloor 4.081 \rfloor = 4$$$.

Given two positive integers $$$l$$$ and $$$r$$$, $$$(l \le r)$$$, find the total number of comic numbers between them (inclusive of $$$l$$$ and $$$r$$$ both).

Input

The first line of the input contains a single integer $$$t$$$ - the number of testcases.

Each testcase consists of one line containing two positive integers $$$l$$$ and $$$r$$$.

$$$1 \le t \le 10^5$$$.

$$$1 \le l \le r \le 10^{18}$$$.

Output

For each testcase, Print the total number of comic numbers between $$$l$$$ and $$$r$$$, $$$[l, r]$$$ (inclusive) in a newline.

Example
Input
2
1 1000000000000000000
3 81
Output
1500002499997
33

E. Gridy
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a grid of size $$$n \cdot m$$$, Each cell of the grid contains "0", "1", or "?". For every "?" We should randomly choose "0" or "1" and put it in there. Now your task is to find the probability that there aren't two adjacent "1" in the grid, For cell $$$(i, j)$$$, all cells $$$(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)$$$ are counted as it's adjacent cells. Print the answer modulo $$$998244353$$$.

Input

In the first line of input, You'll receive two integers $$$n$$$ and $$$m$$$ which $$$n$$$ shows the number of rows and $$$m$$$ shows the number of columns.

$$$1 \le n, m \le 15$$$.

In the second line you'll receive a grid of size $$$n \cdot m$$$ which only contains of "?", "0" or "1".

Output

Print the answer modulo $$$998244353$$$.

Examples
Input
2 5
0?100
1000?
Output
499122177
Input
2 2
?1
01
Output
0

F. CLC Loves SQRT Technology (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$.

You have an array of length $$$n$$$, We declare function $$$f(x)$$$ for a non-empty subsequence of the array as the minimum number of moves needed to change the subsequence's elements to make the subsequence $$$palindrome$$$. The move is defined as follows.

  • Select an element from the subsequence, and change the value to any arbitrary value.

Now your task is to find sum of $$$f(x)$$$ for all non-empty subsequences of the array.

Input

In the first line of input You'll be given number $$$n$$$ which shows the length of the array.

In the second line You'll receive the array.

$$$1 \le n \le 10^3$$$.

$$$1 \le a_i \le n$$$.

Output

Print an integer representing the sum of $$$f(x)$$$ for all non-empty subsequences, as the answer may be large, Print it modulo $$$998244353$$$.

Examples
Input
5
4 2 4 3 5
Output
30
Input
10
2 2 1 1 3 2 3 4 1 3
Output
1969
Input
5
2 5 3 1 4
Output
32

G. CLC Loves SQRT Technology (Hard Version)
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$.

You have an array of length $$$n$$$, We declare function $$$f(x)$$$ for a non-empty subsequence of the array as the minimum number of moves needed to change the subsequence's elements to make the subsequence $$$palindrome$$$. The move is defined as follows.

  • Select an element from the subsequence, and change the value to any arbitrary value.

Now your task is to find sum of $$$f(x)$$$ for all non-empty subsequences of the array.

Input

In the first line of input You'll be given number $$$n$$$ which shows the length of the array.

In the second line You'll receive the array.

$$$1 \le n \le 10^5$$$.

$$$1 \le a_i \le n$$$.

Output

Print an integer representing the sum of $$$f(x)$$$ for all non-empty subsequences, as the answer may be large, Print it modulo $$$998244353$$$.

Examples
Input
5
4 2 4 3 5
Output
30
Input
10
2 2 1 1 3 2 3 4 1 3
Output
1969
Input
5
2 5 3 1 4
Output
32