CodEMI 2025
A. Supermarket
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are at a $$$1$$$ dollar supermarket where there are $$$n$$$ sub-shops, each second a new customer comes in every shop, $$$\bf {\text{inititally all of them are empty}}$$$.

Since this is a $$$1$$$ dollar supermarket there is only one worker. Each second this worker chooses uniformaly randomly a shop and serves all it's customers instantly.

To do some savings the boss doesn't hire extra workers unless $$$\bf{\text{all}}$$$ the shops are all floaded. That is if we denote the number of customers of the $$$i-$$$th shop to be $$$a_i$$$.

Then the shops are floaded whenever forall $$$i \in [1, n], a_i \ge b_i$$$ for some pre-fixed $$$b_i$$$.

- $$$\bf{\text{Extra constraints : }}$$$ we assume that $$$b_1 = 0$$$.

One may prove that the shops will be floaded almost certaintly, your task is to calculate the expected time at which the boss will have to hire extra workers.

It can be shown that the answer can be represented as $$$\frac{P}{Q}$$$, where P and Q are coprime integers and $$$Q \not \equiv 0$$$ mod $$$10^9 + 7$$$. Print the value of $$$P\cdot Q^{-1}$$$ mod $$$10^9+7$$$.

Input

The first line of the input you will be given $$$1 \le n \le 2 \cdot 10^5$$$ the number of shops.

The second line of the input contains $$$n$$$ space separated integers $$$b_1, ... b_n (0 \le b_i \le 10^{18})$$$ and $$$b_1 = 0$$$.

Output

Output a single integer the expected time at which the boss will have to hire extra workers modulo $$$10^9 + 7$$$.

Examples
Input
3
0 1 1
Output
3
Input
8
0 7 5 6 7 10 6 7
Output
149135259

B. Data Center Lamps
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a busy data center, lamps are essential for smooth server operations. One day, several lamps go out, making it hard for technicians to work. To fix this, the facility uses a special control panel that can toggle all lamps in a selected row or column — flipping each lamp from on to off or off to on.

Your task is to help restore full lighting using the fewest toggles. If it's impossible to turn all lamps on, output $$$-1$$$.

You're given an $$$n \times m$$$ grid representing lamp states: $$$1$$$ for on, $$$0$$$ for off. With each operation, you can toggle any row or column to flip all its lamp states.

Determine the minimum number of toggles needed to turn every lamp on, or report $$$-1$$$ if it's not possible.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2500$$$) — the number of rows and columns in the grid.

The next $$$n$$$ lines each contain $$$m$$$ integers (either $$$0$$$ or $$$1$$$) describing the grid.

Output

For each test case, print a single integer $$$-$$$ the minimum number of toggles required to make all lamps on, or $$$-1$$$ if it is impossible.

Examples
Input
3 3
0 1 0
1 0 1
0 1 0
Output
3
Input
4 4
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
Output
4
Input
4 4
0 0 0 1
0 0 0 1
0 0 0 0
0 0 0 0
Output
-1
Note

$$$$$$ \begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} \xrightarrow{\text{Row 2}} \begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix} \xrightarrow{\text{Col 1}} \begin{matrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \end{matrix} \xrightarrow{\text{Col 3}} \begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} $$$$$$

C. OR-Max Segments
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Imran is working with arrays and bitwise operations. One day, he discovered an interesting property in subarrays. He calls a segment Cool if it satisfies a unique condition involving the maximum value and the bitwise OR of the elements.

You're given an array of integers $$$a$$$. A cool segment is a subarray $$$[l,r]$$$ such that: $$$$$$ \max(a_l, a_{l+1}, \dots, a_r) = a_l \,|\, a_{l+1} \,|\, \dots \,|\, a_r $$$$$$

In simple terms, the maximum value in the segment must be exactly equal to the bitwise OR of all the elements in that segment.

Your task is to count how many such cool segments exist in the array.

Input

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

For each test case:

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ — the number of elements in the array.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \cdots, a_n$$$ $$$(0 \leq a_i \lt 2^{30})$$$ — the elements of the array.

The total sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$

Output

For each test case, output a single integer — the number of cool segments in the array.

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

All Subarrays: $$$[1], [2], [3], [2], [1,2]$$$ (Not Cool), $$$[2,3], [3,2], [1,2,3], [2,3,2], [1,2,3,2]$$$

Total Cool Segments: $$$9$$$

D. RGB Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Imran owns a magical tree with $$$n$$$ nodes, where the root node is numbered $$$1$$$. Each node in this tree is colored either Red (R), Green (G), or Blue (B).

Imran has a magic wand that allows him to invert the colors of a node and all its descendants in the tree (i.e., the entire subtree rooted at that node). The color inversion follows this cyclic pattern:

$$$$$$\textbf{Red (R)} \to \textbf{Green (G)} \to \textbf{Blue (B)} \to \textbf{Red (R)}$$$$$$

Imran will perform $$$q$$$ operations on the tree. For each operation, he selects a node and uses his wand to invert the colors of all nodes in the subtree rooted at that node.

Your task is to determine the final color of each node after all $$$q$$$ operations have been completed.

Input

The first line contains a positive integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$, representing the number of nodes in the tree.

The second line contains $$$n-1$$$ integers $$$p_i$$$ $$$(1 \leq p_i \leq n)$$$, where $$$p_i$$$ indicates the parent of node $$$i+1$$$ in the tree.

The third line is a string of length $$$n$$$ consisting of the characters R, G, and B, where the $$$i$$$-th character represents the initial color of the $$$i$$$-th node.

The fourth line contains a positive integer $$$q$$$ $$$(1 \leq q \leq 2 \cdot 10^5)$$$, representing the number of operations.

The next $$$q$$$ lines each contain a single integer $$$q_i$$$ $$$(1 \leq q_i \leq n)$$$, specifying the node on which the $$$i$$$-th operation is performed.

Output

Output a single string of length $$$n$$$, where the $$$i$$$-th character represents the final color of the $$$i$$$-th node after all operations.

Example
Input
7
1 1 2 3 3 2
RGBGRRB
4
5
1
2
7
Output
GRRRBGB
Note

After the 1st query, the tree becomes: RGBGGRB.

After the 2nd query, the tree becomes: GBRBBGR.

After the 3rd query, the tree becomes: GRRRBGG.

After the 4th query, the tree becomes: GRRRBGB.

E. Binary Mirror Maze
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the Binary Mirror Maze!

We start with an empty bit string: $$$s_0$$$ = ""

Then, for each integer $$$i \geq 0$$$, construct the next string as follows: $$$s_{i+1} = s_i +$$$ "$$$0$$$" + mirror($$$s_i$$$) Here, mirror(s) means that we first reverse the string s, and then invert each bit (swap every "$$$0$$$" with "$$$1$$$" and every "$$$1$$$" with "$$$0$$$").

For example:

  • For $$$s_0$$$ = "", we have: $$$s_1$$$ = "" + "0" + mirror("") = "0"

  • For $$$s_1$$$ = "0", since mirror("0") = "1", we get: $$$s_2$$$ = "0" + "0" + "1" = "001"

  • For $$$s_2$$$ = "001": mirror("001") → reverse("001") = "100", then invert to obtain "011" Thus, $$$s_3$$$ = "001" + "0" + "011" = "0010011"
It can be shown that every string $$$s_i$$$ is a prefix of an infinitely long bit string t.

Your task is: Given an integer k, find the k-th character (1-indexed) of the string t.

Input

In the first line you will be given an integer $$$T (1 \le T \le 10^5)$$$ the number of test cases. Each of the next $$$T$$$ following lines you will be given a single integer $$$k(1 \le k \le 10^{18})$$$.

Output

For each integer $$$k$$$ output the $$$k-th$$$ caracter in the infinitely long string $$$t$$$.

Example
Input
5
2
9
6
4
5
Output
0
0
1
0
0

F. Classroom
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

- Imagine you have $$$n$$$ students lined up, each with an integer value. Your challenge is to split this line into one or more consecutive groups (the number of groups $$$m$$$ is not fixed) such that each group meets a special "hull" condition:

  • The first group starts with student $$$1$$$ and the last group ends with student $$$n$$$.
  • The groups are consecutive; if group $$$j$$$ covers students from index $$$l_j$$$ to $$$r_j$$$, then for every $$$1 \le j \lt m$$$, we have $$$r_j + 1= l_{j+1}$$$.
  • For each group $$$j$$$ (where $$$1 \le j \le m$$$), if the group includes students with index $$$l_j, l_j+1, \dots, r_j$$$, then the sum $$$l_j + l_j+1 + \dots + r_j$$$ must be divisible by $$$j$$$.

- Your task: Compute the number of ways to form such a segmentation of the students, and output your answer modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 5*10^3$$$) — the number of students.

Output

Print a single integer: the number of valid segmentations, modulo $$$10^9 + 7$$$.

Examples
Input
7
Output
5
Input
5
Output
5

G. Arithmetic sequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Find the number of finite arithmetic sequences with a common difference of $$$D$$$ and a total sum $$$S$$$.

That is find the number of sequences $$$u_0, ... u_n$$$ for some such that forall $$$0 \le i \lt n, u_{i + 1} - u_{i} = D$$$ and $$$u_0 + ... u_n = S$$$.

Input

Input you will be given two integers $$$D, S (1 \le S \le 10^{12}, 1 \le D \le 10^{18})$$$

Output

Output the number of finite arithmetic sequences with a common difference of $$$D$$$ and a total sum of $$$S$$$.

Example
Input
1 8
Output
1

H. Detective Korombo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

At the scene of a strange break-in, Korombo finds a slip of paper with cryptic clues, all pointing to a secret locker containing the key to the case. The lockers are numbered with integers from $$$-\infty$$$ to $$$+\infty$$$, and each clue gives an inequality that narrows down the possible number $$$x$$$ of the locker.

The inequalities are of the form:

$$$$$$ \texttt{x \gt a} \quad \quad \quad \texttt{x \gt = a} \quad \quad \quad \texttt{x \lt a} \quad \quad \quad \texttt{x \lt = a} $$$$$$ Your task is to help Korombo determine whether there is exactly one integer $$$x$$$ that satisfies all the clues.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of constraints.

Each of the next $$$n$$$ lines contains a constraint in one of the following four forms:

  • > a
  • >= a
  • < a
  • <= a

Where $$$a$$$ is an integer with absolute value at most $$$10^9$$$.

Output

Print the result on a single line:

  • The unique integer $$$x$$$ satisfying all the constraints, if it exists.
  • NOT UNIQUE if multiple integers satisfy the constraints (insen).
  • IMPOSSIBLE if no integers satisfy the constraints.

The answer is case-insensitive. For example, IMPOSSIBLE, Impossible, or impossible will all be accepted.

Examples
Input
4
> 5
>= 6
< 8
<= 6
Output
6
Input
2
> 2
<= 5
Output
NOT UNIQUE
Input
2
>= 10
< 10
Output
IMPOSSIBLE

I. Quantum Flips
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You work at a secret communications office, where every day you handle mysterious messages encoded in lowercase letters. One day, you receive two messages, both containing exactly the same number of letters. Your mission is to transform the first message $$$S$$$ into the second message $$$T$$$ using a very special operation.

The operation you can perform consists of two parts:

  1. Swap: Choose two distinct positions $$$i$$$ and $$$j$$$ in the message, and swap the letters at these positions.
  2. Quantum Flip: For every letter that lies strictly between positions $$$i$$$ and $$$j$$$ (i.e. from $$$\min(i, j) + 1$$$ to $$$\max(i, j) - 1$$$), change it to its complementary letter. The complementary letter is defined such that $$$\text{flip}(\text{'a'}) = \text{'z'}$$$, $$$\text{flip}(\text{'b'}) = \text{'y'}$$$, ..., $$$\text{flip}(\text{'z'}) = \text{'a'}$$$.

Note: If the chosen indices $$$i$$$ and $$$j$$$ are adjacent, the operation simply swaps the two letters, as there are no letters between them to flip.

Your goal is to determine the minimum number of operations required to transform $$$S$$$ into $$$T$$$. If it is impossible to transform $$$S$$$ into $$$T$$$ using these operations, output $$$-1$$$.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 7$$$) — the length of the strings.

The second line contains a string $$$S$$$ of length $$$n$$$, consisting of lowercase English letters.

The third line contains a string $$$T$$$ of length $$$n$$$, also consisting of lowercase English letters.

Output

Print a single integer: the minimum number of operations required to transform $$$S$$$ into $$$T$$$, or $$$-1$$$ if it is impossible.

Examples
Input
3
abc
xyz
Output
7
Input
6
codemi
meowic
Output
6
Input
3
cde
eyd
Output
-1
Note

Testcase 1: $$$$$$ \begin{array}{rcl} \texttt{abc} \xrightarrow{\text{1}} \texttt{cya} \xrightarrow{\text{2}} \texttt{yca} \xrightarrow{\text{3}} \texttt{axy} \xrightarrow{\text{4}} \texttt{xay} \xrightarrow{\text{5}} \texttt{yzx} \xrightarrow{\text{6}} \texttt{yxz} \xrightarrow{\text{7}} \texttt{xyz} \end{array}$$$$$$

J. How did we get here?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given Speed, Haste, Strength, Instant Health, Regeneration, Resistance, Fire Resistance, Jump Boost, Nausea, Weakness, Poison, Wither, Health Boost, Absorption, Saturation, Glowing, Bad Omen, Levitation, Dolphin's Grace, Conduit Power, Water Breathing, Slow Falling, Luck, Bad Luck.

Since the answer can be very small, print it modulo answer+1.

Input

A lot of pairs of positif integers

Output

A lot of single integers

Example
Input
6
0 3
0 4
0 5
4 9
73267 73267
23 1238916
Output
6
10
15
39
73267
767457046733