You are given an array $$$A$$$ of length $$$N$$$. Count the number of subarrays$$$^\dagger$$$ such that the number of elements divisible by $$$K$$$ is divisible by $$$K$$$.

$$$\dagger$$$  A subarray is obtained by deleting several (possibly zero) elements from the start of the array and several (possibly zero) elements from the end of the array.

There are $$$N$$$ computers; each one is either turned on or off.

The computers are connected to each other by $$$N - 1$$$ cables; the connections form a tree$$$^\dagger$$$.

You can do the following operation:

• Switch the state of one computer and all the computers that are directly connected to it by a cable.

Determine whether it is possible to make all the computers turned on.

$$$\dagger$$$  A tree is a connected undirected graph with $$$N$$$ nodes and $$$N - 1$$$ edges.

Given a string $$$S$$$ of length $$$N$$$, find the length of the longest substring$$$^\dagger$$$ $$$R$$$ such that: $$$$$$\sum_{c=\texttt{'a'}}^{\texttt{'z'}} freq[c] \cdot C \ge |R| \cdot max(R)$$$$$$

Where:

• $$$freq[c]$$$ is the frequency of the character $$$c$$$ in the substring $$$R$$$.

• $$$C$$$ is the value of the character $$$c$$$ (the letter 'a' has a value of $$$1$$$, the letter 'b' has a value of $$$2$$$, and so on).

• $$$|R|$$$ is the length of the substring $$$R$$$.

• $$$max(R)$$$ is the greatest value of a character in the substring $$$R$$$.

$$$\dagger$$$  Substring: obtained by deleting several (possibly zero) characters from the start of the string and several (possibly zero) characters from the end of the string.

Given an array $$$A$$$ of length $$$N$$$, and a positive integer $$$K$$$.

Consider the following procedure to determine whether a subarray$$$^\dagger$$$ $$$A[L \dots R]$$$ is considered good or not:

• Let's create a copy of this subarray, let's call it $$$C$$$ of length $$$R - L + 1$$$.
• Let's define $$$S$$$ as the maximum subarray sum$$$^\ddagger$$$ in $$$C$$$.
• If $$$S = K$$$, then the subarray $$$A[L \dots R]$$$ is good; otherwise, it is not good.

Your task is to count the number of good subarrays in $$$A$$$.

$$$\dagger$$$ A subarray is obtained by deleting several (possibly zero) elements from the start of the array and several (possibly zero) elements from the end of the array.

$$$\ddagger$$$ The maximum subarray sum in an array $$$B$$$ of length $$$M$$$ is equal to the maximum value of $$$B_L + B_{L + 1} + ... + B_R$$$ over all pairs of integers $$$L$$$, $$$R$$$ such that $$$1 \le L \le R \le M$$$.

Given an array $$$A$$$ consisting of $$$N$$$ positive integers.

A sequence of integers is considered $$$\textbf{good}$$$ if the following condition holds:

• Let $$$X$$$ be equal to the bitwise XOR of all elements in the sequence; then $$$X$$$ must have an odd number of on bits (bits that are equal to $$$1$$$) in its binary representation.

Your task is to count the number of different$$$^\ddagger$$$ non-empty good subsequences$$$^\dagger$$$ of $$$A$$$. Since the answer can be very large, print the answer modulo $$$10^9 + 7$$$.

$$$\dagger$$$  A sequence $$$B$$$ is a subsequence of $$$A$$$ if $$$B$$$ can be obtained from $$$A$$$ by deleting several (possibly none or all) elements (not necessarily adjacent).

$$$\ddagger$$$  Two subsequences are considered different if the sets of indexes of their elements in the original sequence are different; that is, the values of the elements are not considered when comparing the subsequences.

In the annual Syrian Collegiate Programming Contest for Private Universities, there's a running joke among teams: the first problem — affectionately called "The Extreme" — is supposed to be the easiest one in the entire contest.

Before the contest begins, coaches often tease the teams with the same iconic question:

"What'll You Do If You Didn't Solve The Extreme?"

The question is always asked exactly this way — with the same wording, the same capitalization, and yes... even the question mark at the end.

If a participant hears this question and responds with:

"I Guess We'll Never Know"

— they're officially forgiven.

Your task is to write a program that reads the exact question from the input and responds with the standard answer.

You are given a string $$$S$$$ of length $$$N$$$ and a set of $$$M$$$ strings $$$\{T_1, T_2, \dots, T_m\}$$$.

You want to select as many non-overlapping substrings$$$^\dagger$$$ of $$$S$$$ as possible such that each selected substring is exactly equal to one of the $$$M$$$ strings.

$$$\dagger$$$  Substring: obtained by deleting several (possibly zero) characters from the start of the string and several (possibly zero) characters from the end of the string.

There is a directed graph consisting of $$$n$$$ levels. Each level $$$i$$$ contains $$$a_i$$$ nodes arranged in a linear sequence.

• Within each level, node $$$j$$$ in level $$$i$$$ has a directed edge to node $$$j+1$$$ for $$$1 \le j \lt a_i$$$.
• Every node in level $$$i$$$ has a directed edge to the first node of level $$$i+1$$$, for $$$1 \le i \lt n$$$.

• Level 1: nodes 1 to 3.
• Level 2: nodes 4 to 6.
• Level 3: nodes 7 and 8.

Alhelue and Ahdali are playing a game on a graph like this. Initially, a stone is placed at the first node in level $$$1$$$. Each player, on their turn, selects a node neighbor to the current stone position and moves the stone directly to that node.

The goal is to move the stone to the last node in level $$$n$$$. The player who performs this final move wins.

You are given:

• An integer $$$n$$$ — the number of levels in the graph.
• An array $$$a = [a_1, a_2, \ldots, a_n]$$$ — where $$$a_i$$$ represents the number of nodes in level $$$i$$$.

Determine which player has a winning strategy assuming both play optimally. The first player always starts.

You are given an array $$$A$$$ consisting of $$$N$$$ positive integers, and a positive integer $$$X$$$.

Count the number of pairs of integers $$$(i, j)$$$ ($$$1 \le i \lt j \le N$$$) that satisfy the following:

• $$$A_i + A_j$$$ must be divisible by $$$X$$$.
• $$$A_i \cdot A_j$$$ must be divisible by $$$X$$$.

Given an array $$$A$$$ consisting of $$$N$$$ positive integers where $$$1 \le A_i \le M$$$.

We define the shift operation as the following:

• Let an integer $$$X$$$ be good if $$$X$$$ appears in $$$A$$$ at least once, and the number of occurrences of $$$X$$$ in the array is even (divisible by $$$2$$$).
• Let $$$S$$$ be the set of indices $$$i$$$ where $$$A_i$$$ is good.
• For each index $$$i$$$ in the set, you must change $$$A_i$$$ into $$$(A_i \bmod M) + 1$$$, where $$$\bmod$$$ is the modulo operation (remainder when divided by $$$M$$$).

You have to process $$$Q$$$ queries of two types:

• $$$1$$$: perform the shift operation.
• $$$2$$$ $$$i$$$: print the value of $$$A_i$$$.

Note that you have to answer $$$T$$$ testcases.

You have to write a program to decide if a student passed an exam or failed it.

A university exam is divided into a practical exam and a theoretical exam.

You should pass the practical exam to be allowed to take the theoretical exam.

The practical exam score is out of $$$40$$$, and the theoretical exam score is out of $$$60$$$. Thus, the total exam score is out of $$$100$$$ points, which is calculated by summing up the scores of the practical and theoretical exams.

You pass the practical exam if you score at least $$$18$$$ out of $$$40$$$, and you pass the full exam if you score at least $$$60$$$ out of $$$100$$$.

Ahdali wants to learn more about math and physics. In his research, he discovered a point in any object called the center of mass. In geometry, one often assumes uniform mass density, in which case the center of mass coincides with the centroid.

Ahdali found this equation for the centroid of a weighted triangle (where all three points have weights): $$$$$$C_x = \frac{a \times x_1 + b \times x_2 + c \times x_3 }{a + b + c}, C_y = \frac{a \times y_1 + b \times y_2 + c \times y_3 }{a + b + c}$$$$$$

where $$$x_i$$$ and $$$y_i$$$ are the coordinates of the $$$i$$$-th point. and $$$a$$$, $$$b$$$, $$$c$$$, are the weights of the first, second and third point. respectively.

Shadi and Taim want to see if Ahdali understood the concept correctly, so they proposed an inverse problem: They will give Ahdali a point and the weights of a triangle (a, b, and c), and Ahdali must find a triangle with these weights and this centroid.

An additional constraint they added is that each of the triangle's sides must be longer than 1.

Whether Ahdali actually completed this task is another tale.

For the time being, you should take a crack at this problem.

Alice has string $$$s$$$ and Bob has string $$$t$$$, both initially equal to the single-character string "a". There are $$$q$$$ operations. Each operation is one of the following:

• $$$1$$$ $$$x$$$ $$$k$$$: append the string $$$x$$$ exactly $$$k$$$ times to Alice's string $$$s$$$.
• $$$2$$$ $$$x$$$ $$$k$$$: append the string $$$x$$$ exactly $$$k$$$ times to Bob's string $$$t$$$.

After each operation, both players may reorder the characters of their current strings to form the lexicographically smallest possible string. They then compare these two strings:

• If Alice's string is smaller, output "Alice".
• If Bob's string is smaller, output "Bob".
• If they are equal, output "Tie".

Both players play optimally at every step. Determine and output the result after each operation.