For Halloween, Mondialu went to each of his neighbors to ask for candies. In order to receive the maximum number of candies, he needs to be as scary as possible.

Mondialu has $$$n$$$ Halloween costumes $$$a_1, a_2, a_3, ... , a_n$$$. He needs to choose a subsequence (a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements) from the $$$n$$$ costumes (yes, Mondialu can wear multiple costumes, this is the level of scariness we are dealing with).

A subsequence is the scariest if it has the following properties:

• Has an even positive length.
• The first half of the subsequence is equal to the second half.
• It is the lexicographically largest subsequence.

An array $$$X$$$ is lexicographically larger than an array $$$Y$$$ if there exist an $$$i$$$ so that $$$x_1 = y_1, x_2 = y_2, ... , x_{i-1} = y_{i-1}$$$ and $$$x_i \gt y_i$$$ or if $$$Y$$$ is a prefix of $$$X$$$.

• $$$1 \le n \le 5$$$ for $$$20$$$ points
• $$$5 \lt n \le 100$$$ for $$$20$$$ points
• $$$100 \lt n \le 1000$$$ for $$$20$$$ points
• $$$1000 \lt n \le 100000$$$ for $$$40$$$ points

Nitoiu found out that he sings really reaally bad so he wants a career change. While expanding his skillset, he discovered that he is very good at arithmetic operations.

His old producer Sake doesn't like the idea of losing a long time collaborator so he wants to discourage Nitoiu by proving that he is not as good at arithmetics as he thinks he is.

Sake gives Nitoiu two integers $$$N$$$, $$$K$$$ and asks him the minimum number of concatenations of $$$N$$$ with itself such that the result is divisible by $$$K$$$. If by concatenating $$$N$$$ with itself any number of times it is impossible to find a multiple of $$$K$$$ the answer is considered $$$-1$$$.

Nitoiu promises that he will cover your favorite song if you help him with this task.

• for 20 points it is guaranteed that $$$N \lt 10$$$, $$$K \leq 18$$$ and the lowest multiple is less than $$$10^{18}$$$
• for another 20 points it is guaranteed that $$$N \lt 10$$$, $$$K \leq 1000$$$ and the result is less than $$$10^4$$$.
• for another 20 points it is guaranteed that $$$N \lt 10$$$, $$$K \leq 10^5$$$ and the result is less than $$$10^7$$$.
• for another 20 points it is guaranteed that $$$N \leq 1000$$$, $$$K \leq 10^5$$$ and the result is less than $$$10^7$$$.
• the last 20 points are given for tests where $$$N \leq 10^9$$$ and $$$K \leq 10^5$$$.

Besides the delicacy that is freshmen blood drank during the Halloween night, Luna also enjoys prime numbers a lot... and the number 3... so she gives you a number $$$N$$$ and demands the number of different ways that the number $$$N$$$ can be written as a sum of 3 prime numbers.

Because you won't risk getting your blood drank by Luna, you decide to answer her demands.

• for 40 points it is guaranteed that $$$N \leq 100$$$
• for another 30 points it is guaranteed that $$$N \leq 5000$$$
• for the other 30 points, $$$N \leq 5\cdot 10^4$$$

While searching in the garbage cans, Jean found a sequence of $$$N$$$ positive integers. Because he has no use for this, he gifted it to Nicusor Gioconda, and gave him a challenge too.

Nicusor has to chose pairwise distinct substrings of length $$$2$$$ such that every index is taken at least once. If he will give a correct partitioning, he will get the ultimate prize: the magical chicken wing!

In this problem, we consider that a substring is a contiguous subset of indices $$$[i,i+1,\cdots j-1, j]$$$.

Because he is far better at singing than he is at solving problems, he asks for your help.

• for 20 point it is guaranteed that $$$N \leq 20$$$
• for the other 80 points we have $$$N \leq 10^5$$$

RMN wasted all his money on sports betting...again. However, he still feels the need of betting just one more time in order to at least recover his losses.

The only issue is that he needs a big sum to get a good return on his last "safe" bet. Because he doesn't have a lot of skills, he can't get this money too easily. Luckily, a man in the parking spot of a gas station offered him 100 RON if he can count how many substrings of an integer sequence have their maximum value between two given values.

More formally, RMN receives an integer sequence $$$A$$$ of $$$N$$$ numbers, and two integers $$$L$$$ and $$$U$$$. He is asked to count how many substrings $$$S = A[i,i+1\cdots j]$$$ have $$$L \leq max(S) \leq U$$$.

Help RMN retire in glory by winning the 100 RON needed for his first win!

P.S. He will probably lose anyway :(

• for 25 points, it is guaranteed that $$$N \leq 500$$$
• for another 25 points, it is guaranteed that $$$N \leq 5000$$$
• for the last 50 points, we have $$$N \leq 10^5$$$

In Scundu, two boys were playing basketball. They are not very good at the game, so they got bored and decided to rest on a bench. While sitting there, they wondered: if a game of basketball ends with the score $$$A$$$ and $$$B$$$, where $$$A$$$ is the score of the first team and $$$B$$$ is the score of the second team, in how many ways can this score be obtained? Because they are not very good at programming either, they need your help to find out.

In Scundu, the basketball rules are the following: depending on the striking distance, each team can get either 2 or 3 points for introducing the ball in the basket. Because scundenians are superior people, we consider that faults will never occur.

• for 30 points, we have $$$ 0 \le A, B \le 10$$$
• for another 20 points, we have $$$A = 0$$$ or $$$B = 0$$$
• for the last 50 points, we have $$$ 0 \le A, B \le 500$$$

In 10660 B.C., we will assume that, in Scundu, there has been the most epic battle to this day (because we can't prove that it didn't happen). The battle between the scundenians (the name of the people from scundu) and the invading forces was very close, so close that it was perfectly even and both sides decided to call for reinforcements. We say that the scundenians won the battle if, in every moment of the battle (since the reinforcements start to arrive), the number of scundenians engaged in battle was greater or equal to the number of invading forces engaged in battle.

Knowing the number $$$N$$$ of scundenians that come as reinforcements, the same $$$N$$$ number of invading forces that come as reinforcements and that at every second there is exactly one soldier arriving at battle (either scundenian or invader), find the number of ways the reinforcements can come so that the scundenians win The Battle of Scundu

We consider that 2 ways of the reinforcements $$$a_0 a_1 ... a_n$$$ and $$$b_0 b_1 ... b_n$$$ to come are different if at any second $$$1 \le i \le n$$$ we have $$$a_i \neq b_i$$$ (where $$$a_i$$$ and $$$b_i$$$ represent the type of the soldier that comes at the second $$$i$$$ , scundenian or invader).

• for 30 points it is guaranteed that $$$N \le 30$$$
• for another 30 points it is guaranteed that $$$N \le 1000$$$
• for the last 40 points, we have $$$N \le 1.000.000$$$

After a tiring practical test at OOP, Rares is faced with a new challenge. He has to solve the following problem, otherwise he will fail the Programming class.

Let $$$v$$$ be an array of $$$n$$$ non-negative integers. Find the maximum value of ($$$v_i$$$ $$$\oplus$$$ $$$v_j$$$) $$$\times$$$ ($$$v_k$$$ + $$$v_l$$$), where $$$1$$$ $$$\le$$$ $$$i \lt j \lt k \lt l$$$ $$$\le$$$ $$$n$$$. Here $$$\oplus$$$ represents the bitwise xor operation.

Help Rares save his GPA!

• For $$$20$$$ points, it is guaranteed that $$$n$$$ $$$\le$$$ $$$200$$$
• For another $$$20$$$ points, it is guaranteed that $$$n$$$ $$$\le$$$ $$$2000$$$
• For the last $$$60$$$ points, we have $$$n \leq 200000$$$

As many of you might know, during the golden age of romanian television, one of the most beloved channels was named OTV.

One of the reasons for its popularity were the polls where the spectators voted for one of two options. Maybe the most popular poll was the one asking who would win in a fight between the dacians and the samurai.

After years and years, the OTV founder, DD, is back with his new project: DD Home Cinema. In order to regain his old level of fame he wants to please the nostalgics by bringing back the famous poll, but with a modern twist!

DD gives his spectators two integer sequences $$$A$$$ (the strenghts of the dacians) and $$$B$$$ (the strengths of the samurai) and wants another sequence $$$C$$$ of the same length, where $$$C_i \in \{A_i, B_i\}$$$ (either the $$$i$$$-th dacian or the $$$i$$$-th samurai). Because such a large sequence would not fit well on a tv display, he asks for his spectators only for the smallest difference in strength of such a sequence.

Formally, the spectators are asked for the minimum value of $$$max(C) - min(C)$$$ among all possible sequences $$$C$$$.

• for 5 points, it is guaranteed that $$$N \leq 2$$$
• for another 15 points, it is guaranteed that $$$N \leq 20$$$
• for another 20 points, it is guaranteed that $$$N \leq 5000$$$
• for the last 60 points, we have $$$N \leq 10^5$$$

After getting bored of playing with the Rubik's Cube and submitting Wrong Answers, Ion decided to move on to more interesting activities. He decided to play a game with his good friend Mario on a one dimensional board which can be represented as an array with $$$n$$$ non-negative integers $$$a_1, a_2, a_3, ... , a_n$$$. The game is played by the following rules:

• They play the game by moving a pawn on the board which is initially placed at position $$$k$$$.
• Ion takes the first move, and they take moves alternatively.
• In any move with the pawn at position $$$i$$$, the current player must move the pawn to the smallest next position $$$j$$$ such that $$$j \gt i$$$ and $$$a_j$$$ differs from $$$a_i$$$ on at most one bit in binary representation.
• The player who can't make any legal move loses the game.

They play this game many times and the board can be modified many times. Ion wants to ask you for some initial states who will win the game.

• for $$$20$$$ points it is guaranteed that $$$n \le 1000$$$ and $$$m \le 1000$$$
• for the other $$$80$$$ points, $$$n \le 200000$$$ and $$$m \le 200000$$$

It is the first day of school and you are in Computer Science class. Your best friend Iuli has a new challenge for you.

He hands you a string consisting of lowercase english characters and asks you to find the length of all its periods.

A period of a string is a prefix of it which has the property that the string can be written as a concatenation of that prefix with itself for a finite number of times.

For example, the periods of $$$aaaaaa$$$ are $$$a, aa, aaa, aaaaaa$$$.

Due to the high ammount of input and output data, it is recommended to code in C++, use streams and the following instructions before reading the input for speedup:

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

• for $$$30$$$ points, it is guaranteed that the sum of lengths of all strings in the input will not exceed $$$10^4$$$
• for another $$$40$$$ points, it is guaranteed that the sum of lengths of all strings in the input will not exceed $$$5\cdot10^6$$$
• for the last $$$30$$$ points, the sum of lengths of all strings in the input will not exceed $$$2\cdot10^7$$$.

Mathematical Final Boss is getting tired from all his success and decided to start playing with some integer sequences.

After a while, he found a very interesting function which he called $$$SAlt$$$. For a sequence of numbers $$$S = a_1, a_2, \cdots a_k$$$, he takes the non-increasing sorted sequence and stars to alternatively add and substract numbers. Formally if the sorted sequence is $$$a_{i_1},a_{i_2},\cdots a_{i_k}$$$, we have $$$SAlt(S) = \sum_{p=1}^{k}(-1)^{(p-1)}\cdot a_{i_p}$$$.

This is too easy for our Final Boss, so, for a sequence of numbers he now wants to compute the sum of the $$$SAlt$$$ values for all its subsets.

Now every morning he takes an integer sequence $$$A$$$ with $$$N$$$ numbers and $$$Q$$$ queries $$$q_i=(l_i,r_i)$$$ that ask for the $$$SAlt$$$ sum of all subsets of numbers of the substring $$$A[l_i,r_i]$$$.

He can do all these computations in less than a second and he is now curious if you can do it too with the help of a modern computer.

Because the numbers can become very large, you have to compute it modulo $$$10^9 + 7$$$.

• for $$$20$$$ points, it is guaranteed that $$$N\leq20$$$ and $$$Q\leq 50$$$.
• for the other $$$80$$$ points, we have $$$N \leq 10^5$$$ and $$$Q \leq 10^5$$$.

As Rares failed his OOP exam mentioned earlier, he tries his luck with this problem hoping to forget his problems. We call an interesting-substring any substring which has at least one minimum value in its second half. $$$[1, 0, 3, 0, 4, 6]$$$ is an interesting substring because its minimum, $$$0$$$ lays in the second half, while $$$[1, 0, 3, 0, 5, 6, 8]$$$ is not an interesting substring as its minimum, $$$0$$$ lays in the first half.

$$$ATTENTION!$$$ If the substring is of odd length, the middle is considered to be a part of the first half

In this problem, we consider that a substring is a contiguous subset of indices $$$[i,i+1,\cdots j-1, j]$$$.

Given an array of $$$N$$$ elements, calculate the number of interesting substrings.

• for 30 points $$$N \leq 200$$$
• for another 30 points, $$$N \leq 5000$$$
• for the last 40 points, $$$N \leq 200000$$$

The scientists at UniBuc have recently discovered an ancient game played by the Dacians called Bitscore. They would write on a piece of paper multiple strictly positive numbers and the players had to choose subsets with the property that the number of digits in the binary form of the numbers create a strictly decreasing sequence. For instance $$$100, 63, 4, 2, 1$$$ is a valid sequence, while $$$100, 64$$$ is not valid.

Given an array of $$$N$$$ numbers compute the number of valid subsets. Because the result can be very big, print the result modulo $$$1000000007$$$.

$$$ATTENTION!$$$ The elements of a subset can be rearranged.

• for 35 points, it is guaranteed that $$$N \leq 15$$$
• for the last 65 points, we have $$$N \leq 100000$$$