Bald was wandering along the beautiful gardens of AUC, when he came across one of his students in competitive programming (CP) — Tourist. Upon meeting, they decided to hold a contest to determine who is the better competitor.
The contest consists of $$$n$$$ problems. Their difficulties are given by a permutation$$$^\dagger$$$ $$$p$$$ of length $$$n$$$, where problem $$$i$$$ has difficulty $$$p_i$$$. If a player solves a problem, its difficulty is added to their score, and the problem is removed from the contest.
The two players take turns. On each turn, the current player chooses one of the remaining problems and solves it. Bald, being overly confident, allows Tourist to start first.
It is known that both players are capable of solving every problem in the contest. In other words, whenever a player chooses a problem, he will successfully solve it. Assuming both players play optimally, determine the winner.
$$$\rule{20em}{0.4pt}$$$
$$$^\dagger$$$ A permutation is a sequence of integers from 1 to n of length n containing each number exactly once. For example, the sequences (1), (5, 4, 1, 2, 3), (1, 3, 2) are permutations, while (1, 1), (4, 3, 1), (2, 3, 4) are not.
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$.
The second line contains $$$n$$$ integers $$$p_1, p_2, p_3, \dots p_n$$$ $$$(1 \leq p_i \leq n)$$$.
It is guaranteed that $$$p$$$ is a permutation.
Output the winner of the contest. If Bald wins, output Bald. Otherwise, output Tourist.
31 3 2
Tourist
In the given example, there are $$$3$$$ problems with difficulties $$$1, 3$$$ and $$$2$$$. The contest proceeds as follows:
- Tourist picks the second problem with difficulty $$$3$$$ and solves it. His score is now 3. Problems $$$1$$$ and $$$3$$$ remain for the next round.
- Bald chooses the third problem with difficulty $$$2$$$, which gets added to his score.
- Finally, Tourist chooses the only remaining problem with difficulty $$$1$$$.
The game ends with Tourist having a score of $$$4$$$, and Bald having a score of $$$2$$$. Hence, Tourist is the winner.
Farouk's course registration opens tonight at midnight, but he's having some trouble logging into banner. Not knowing what a password manager is, Farouk still creates his own passwords and writes them down in his notebook. He generates his passwords in an interesting way. He starts with a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters. Then, he is only allowed to make the following operation:
- Select two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) such that $$$i \oplus j \lt \min(i, j)$$$$$$^{\text{∗}}$$$ and swap the letters at those indices.
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.
$$$^{\text{∗}}$$$$$$\oplus$$$ denotes the bitwise XOR operation.
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) – the number of test cases.
The only line of each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) consisting of lowercase English letters, where $$$|s|$$$ denotes the length of the string.
It is guaranteed that the the sum of $$$|s|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case output a single string – the lexicographically minimum string that can be reached from the starting string.
4dogabcdefghgoodpasswordonetwothreefour
dgoabcdefghgooadpsdorswoenottweefhorru
In the first test case, o and g can be swapped since $$$2 \oplus 3 = 1 \lt 2 = \min(2, 3)$$$ to get "dgo" which is the lexicographically smallest arrangement ($$$d \le g \le o$$$).
In the second test case, no operations were performed since it is already lexicographically smallest.
Meda and Mohamed Hazem are competitive programmers who love exploring number theory puzzles. One day, Meda challanged Mohamed Hazem with a problem:
Let $$$\tau(n)$$$ be the number of positive divisors of $$$n$$$.
Given a positive integer $$$n$$$, find the number of ordered pairs $$$(a, b)$$$ such that $$$1 \leq a, b \leq n$$$ satisfing the following inequality
$$$$$$\tau(a) + \tau(b) \lt \tau(\gcd(a, b)) + \tau(\text{lcm}(a,b))$$$$$$
Note that $$$(2, 3)$$$ and $$$(3, 2)$$$ are not considered the same.
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of the test cases follows.
The only line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$.
For each test case, output a single integer, the number of pairs satisfying the given inequality.
3 2 3 4
0 2 4
In the second test case, it can be shown that only the pairs $$$(2, 3)$$$ and $$$(3, 2)$$$ satisfy the inequality.
$$$\tau(2) = 2$$$, $$$\tau(3) = 2$$$, $$$\tau(\gcd(2,3))= \tau(1) = 1$$$, and $$$\tau(\text{lcm}(2,3)) = \tau(6) = 4$$$
Obviously, $$$2 + 2 \lt 1 + 4$$$ is true.
After a long and exhausting semester, Bald decided to take a break and reflect. However, he remembered that he had been studying discrete mathematics throughout the semester. So, he came up with a problem to challenge his professor, Dr. Daoud.
Bald will give Siniora two coprime$$$^\dagger$$$ non-negative integers $$$a$$$ and $$$b$$$. The challenge for Siniora is to find an integer $$$1 \lt c \leq 2^{63} - 1$$$ that is coprime with both $$$a$$$ and $$$b$$$, or report that no such integer exists.
Dr. Daoud thinks this task is so trivial that he won't even bother solving it himself. Instead, he has decided to assign the task to you.
$$$\rule{20em}{0.4pt}$$$
$$$^\dagger$$$ Two non-negative integers are said to be coprime if their greatest common divisor (GCD) is equal to $$$1$$$. For instance, the integers 3 and 10 are coprime since $$$\text{gcd(3, 10) = 1}$$$, while 5 and 10 are not coprime as $$$\text{gcd(5, 10) = 5}$$$.
Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ $$$(1 \leq t \leq 10^6)$$$ — the number of test cases.
The single line of each test case contains two integers $$$a, b$$$ $$$(0 \leq a, b \leq 10^{18})$$$.
It is guaranteed that $$$a$$$ and $$$b$$$ are coprime.
Output any integer $$$1 \lt c \leq 2^{63} - 1$$$ that is coprime with both $$$a$$$ and $$$b$$$. If no such integer exits, output $$$-1$$$.
44 93 1020 2910000000 10000001
5 7 3 3
For the first test case, we have $$$a = 4$$$ and $$$b = 9$$$. So, we output $$$5$$$. It is clear that $$$5$$$ is coprime with both $$$4$$$ and $$$9$$$.
Note that there are other valid values for $$$c$$$, such as $$$7, 11, 19, 25$$$.
One day, Farouk was playing with a set of equilateral triangles and rods of various lengths. In this game, he chooses three rods, and he wants to place them inside some triangle such that they all meet at a point, and each one touches a side of the triangle at a right angle. He found this very satisfying and so he decided to ask for your help.
You are given an array of distinct even integers $$$l_1, l_2, \cdots, l_n$$$ representing the side lengths of $$$n$$$ equilateral triangles. You will be given $$$q$$$ queries where each query consists of three integers $$$d_1,$$$ $$$d_2$$$, and $$$d_3$$$ representing the squared perpendicular distances to the sides of the triangle. For each query, output the index of any triangle which contains a valid point $$$P$$$ strictly inside the triangle such that the perpendicular distances from $$$P$$$ to the sides of the triangles satisfy the distances given in the query, or determine that no such triangle exists.
The first line contains two integers $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) and $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of triangles and the number of queries, respectively.
The second line contains $$$n$$$ distinct even integers $$$l_i$$$ ($$$1 \le l_i \le 10^6$$$) — the side lengths of the equilateral triangles.
Each of the following $$$q$$$ lines contains three integers $$$d_1,$$$ $$$d_2$$$, and $$$d_3$$$ ($$$0 \lt d_1, d_2, d_3 \le 10^{18}$$$) — the squared perpendicular distances to each side of a triangle.
For each query, output the index of any triangle which contains some point whose perpendicular distances matches those of the query. If there are multiple solutions, output any of them. If no triangle satisfies the query, output -1 instead.
3 3 14 6 12 3 3 3 48 3 12 24 6 6
2 1 -1
10 5 86 52 32 66 88 62 6 98 68 16 5716 2585 2439 363 48 3 4655 735 5309 5109 468 2471 6627 3 3
-1 3 -1 -1 8
In the first test, the following illustrations show valid points for the first and second queries.
 |  |
| Triangle with side length 6 satisfying the first query. | Triangle with side length 14 satisfying the second query. |
For the third query, it can be shown that none of the given triangles contain a point with the required distances.
Meda is standing at stone $$$0$$$. There are $$$n + 1$$$ stones in a line, numbered $$$0, 1, 2, \dots, n$$$.
You are also given an array $$$a$$$ of length $$$n+1$$$, where $$$a_i$$$ is written on stone $$$i$$$.
From stone $$$i$$$, Meda can jump to any stone $$$j \gt i$$$ if $$$(j - i)$$$ divides $$$a_j$$$ (i.e. $$$a_j \bmod (j-i) = 0$$$).
Meda wants to reach stone $$$n$$$ starting from stone $$$0$$$. Find the minimum number of jumps required. If it is impossible, print $$$-1$$$.
The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the size of the array.
The second line contains $$$n+1$$$ integers $$$a_0, a_1, \dots, a_n$$$ $$$(1 \leq a_i \leq 10^5)$$$.
Print a single integer — the minimum number of jumps to reach stone $$$n$$$, or $$$-1$$$ if it is impossible.
6 1 8 3 4 1 2 1
4
10 7 8 2 2 3 4 9 6 1 2 3
3
In the first testcase, the path is:
- $$$0 \to 1$$$, since $$$8 \bmod (1 - 0) = 0$$$.
- $$$1 \to 3$$$, since $$$4 \bmod (3 - 1) = 0$$$.
- $$$3 \to 5$$$, since $$$2 \bmod (5 - 3) = 0$$$.
- $$$5 \to 6$$$, since $$$1 \bmod (6 - 5) = 0$$$.
It was a hot summer day when Bald stumbled upon an interesting problem in Graph Theory. After many failed attempts to solve it, he decided to seek help from the only person he knows at his university who teaches the subject, Dr. Isabel.
You are given a tree$$$^\dagger$$$ with $$$n$$$ vertices. Among them, there are $$$k$$$ special vertices $$$a_1, a_2, a_3, \dots ,a_k$$$, each contains a single token. All other vertices do not contain any tokens. Let $$$X$$$ denote the maximum number of tokens that can be collected by taking any simple$$$^\ddagger$$$ path in the tree.
You will be given $$$q$$$ queries. Each query is described by a single vertex $$$u_i$$$. To answer the $$$i$$$-th query, you need to decide if you can collect $$$X$$$ tokens by taking any path that starts at $$$u_i$$$
Now Dr. Isabel was a little bit busy playing around with matrices. As one of her best students, you decided to take on this task.
$$$\rule{20em}{0.4pt}$$$
$$$^\dagger$$$ A tree is a connected graph with no cycles.
$$$^\ddagger$$$ A simple path is a path in which no vertex is repeated.
Each test contains multiple test cases. The first line of each test 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, k$$$, and $$$q$$$ $$$(1 \leq n \leq 3 \cdot 10^5, 0 \leq k \leq n, 1 \leq q \leq 3 \cdot 10^5)$$$ — the number of vertices, number of special vertices, and number of queries, respectively.
The second line of each test case contains $$$k$$$ integers $$$a_1, a_2, a_3, \dots ,a_k$$$ — denoting the indices of the special vertices.
Then follow $$$n - 1$$$ lines that describe the tree. Each of them contains two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n)$$$ — indices of vertices connected by the $$$i$$$-th edge.
The last line of each test case contains $$$q$$$ integers $$$u_1, u_2, u_3, \cdots, u_q$$$ — the indices of the vertices you must find the answer for.
For each test case, output the answer for each of the $$$q$$$ queries on a single line. For the $$$i$$$-th query, if you can collect $$$X$$$ tokens by taking any path starting at $$$u_i$$$, output JA. Otherwise, output NEIN.
You can output the answer in any case (upper or lower). For example, the strings "JA", "Ja", "jA", and "ja" will be recognized as positive responses.
25 5 31 2 3 4 51 22 33 44 51 3 413 8 62 4 5 6 10 13 11 121 22 33 44 55 66 72 103 88 94 114 124 132 5 6 9 10 13
JANEINNEINNEINNEINJANEINJANEIN
In the second test case, the tree looks as follows:
Special nodes are in blue You can see that the maximum number of tokens that can be collected is $$$X = 5$$$. Among the vertices given in the queries, you can only start at vertices $$$6$$$ or $$$10$$$, and still collect $$$X$$$ tokens.
Farouk has a very long piece of tape divided into cells extending into the positive and negative directions. The cells are indexed by the integers and are colored in alternating black and white segments of equal length. For example, a valid coloring is 3 black cells, followed by 3 white cells, then 3 black cells, and so on. However, as Farouk is quite short, he can't see the entire tape at once and can only ask about the color of one cell at a time. Help Farouk determine the length of the segments in no more than $$$2000$$$ queries.
It is guaranteed that the tape contains at least 5 complete segments.
Each test contains multiple test cases. The first and only line contains $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.
For each test case, there is initially no input.
To ask about the color of a cell, output a line in the following format:
- $$$\textbf{? } x$$$ ($$$-10^{18} \le x \le 10^{18}$$$)
The jury will reply with a line containing either "B" or "W" — the color of cell $$$x$$$.
Once you have determined the length of the segments, output a line in the following format:
- $$$\textbf{! } L$$$
Where $$$L$$$ ($$$1 \le L \le 10^{18}$$$) denotes the length of the segments.
Note that outputting the length does not count towards the query limit.
If your solution exceeds $$$2000$$$ queries in one test case, your program must terminate immediately to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.
After outputting a query, do not forget to output the end of the line and flush the output. Otherwise, you may get Idleness limit exceeded or some other verdict. To do this, use the following:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- see the documentation for other languages.
The interactor is non-adaptive; the coloring is determined before the interaction starts.
Example of interaction:
| Solution | Jury |
| ? 0 | |
| B | |
| ? 1 | |
| B | |
| ? 2 | |
| W | |
| ? 3 | |
| W | |
| ? 4 | |
| W | |
| ? 5 | |
| B | |
| ! 3 |
Meda was studying his favorite subject — Number theory.
He came across Euler's Totient function, which for $$$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k},$$$ is defined as $$$$$$\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right).$$$$$$ where $$$p_1, p_2, \ldots, p_k$$$ are the distinct prime factors of $$$n$$$.
Although Meda loves number theory, he did not pay attention while studying. So, he defined Euler's Totient function as follows $$$$$$ f(n) = \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right), $$$$$$
Meda was then given an array of integers $$$a_1, a_2, \ldots, a_n$$$. He computes $$$f(a_i)$$$ for each $$$1 \leq i \leq n$$$.
Your task is to determine how many distinct rational numbers appear among Meda's results.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(2 \leq a_i \leq 10^6)$$$.
A single integer representing the number of distinct rational numbers among $$$ f(a_1), f(a_2), \ldots, f(a_n) $$$.
3 2 3 4
2
6 3 9 93842 123 2 1024
4
In the first testcase, Let's compute $$$f(a)$$$ for each element.
- For $$$a_1 = 2$$$: the prime divisors are $$$\{2\}$$$, so $$$f(2) = 1 - \tfrac{1}{2} = \tfrac{1}{2}.$$$
- For $$$a_2 = 3$$$: the prime divisors are $$$\{3\}$$$, so $$$f(3) = 1 - \tfrac{1}{3} = \tfrac{2}{3}.$$$
- For $$$a_3 = 4$$$: the prime divisors are $$$\{2\}$$$ (since $$$4 = 2^2$$$), so $$$f(4) = 1 - \tfrac{1}{2} = \tfrac{1}{2}.$$$
Bald is taking Calculus this semester. His professor, Dr. Eslam, often talks about graphs of functions. When Bald later encountered a problem in Graph Theory, he mistakenly thought it was the same kind of "graph". Confused, he went back to Dr. Eslam for help.
You are given an undirected connected graph$$$^\dagger$$$ $$$G$$$ consisting of $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$.
Let $$$f_G(v)$$$ denote the maximum number of distinct vertices that can be visited starting from vertex $$$v$$$ in a graph $$$G$$$.
Consider the following random experiment to sample a pair $$$(G', v)$$$ from $$$G$$$ (where $$$G'$$$ is a graph and $$$v$$$ is a vertex in $$$G'$$$):
- Sample a vertex $$$v$$$ uniformly at random from $$$\{1,2,\dots,n\}$$$.
- If $$$\deg(v) \ge 1$$$, sample an edge $$$e$$$ incident on $$$v$$$ uniformly at random.
- Let $$$G'$$$ be the graph obtained by deleting $$$e$$$ from $$$G$$$ (if $$$\deg(v)=0$$$, then $$$G'=G$$$).
- Return the pair $$$(G',v)$$$.
Your task is to compute the expected value of $$$f_{G'}(v)$$$ over all sampled $$$(G', v)$$$ by the above experiment.
Since the answer can be a rational number, output it modulo $$$10^9+7$$$. Formally, if the expected value is $$$\tfrac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are integers and $$$q \not\equiv 0 \pmod{10^9+7}$$$, then you should output $$$p \cdot q^{-1} \bmod (10^9+7)$$$ where $$$q^{-1}$$$ denotes the modular inverse of $$$q$$$ modulo $$$10^9+7$$$.
Dr. Eslam does not like this kind of graphs; he likes the other type. So you are now in charge of solving this problem for Bald.
$$$\rule{20em}{0.4pt}$$$
$$$^\dagger$$$ A connected undirected graph is a graph containing vertices and edges where each edge can be traversed in either direction, and there is a path (a sequence of edges) between any two vertices in the graph.
The input consists of multiple test cases.
The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — the number of test cases.
Each test case begins with a line containing two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$n - 1 \leq m \leq \min(2 \cdot 10^5, \tfrac{n(n-1)}{2}$$$)) — the number of vertices and edges in the graph.
Then $$$m$$$ lines follow, each containing two integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — describing an undirected edge between vertices $$$u_i$$$ and $$$v_i$$$.
It is guaranteed that:
- the graph is connected,
- there are no self-loops or multiple edges,
- the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$,
- the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
33 21 22 37 71 21 31 51 63 43 65 74 41 22 32 43 4
333333337 845238105 166666671
Consider the first test case, where the graph is a path with $$$n=3$$$ and edges $$$1-2,2-3$$$. Let us consider each vertex separately:
- Start at vertex $$$1$$$: it has degree $$$1$$$. Deleting its only edge leaves it alone, so you can not visit any other vertices. Hence, its contribution is $$$1.$$$
- Start at vertex $$$2$$$: it has degree $$$2$$$. Deleting edge $$$2-1$$$ would enable you to visit vertices $$$2$$$ and $$$3$$$; deleting $$$2-3$$$ leaves would enable you to visit vertices $$$2$$$ and $$$1$$$. Summed over its incident edges this gives a contribution of $$$\frac{2 + 2}{2} = 2.$$$
- Start at vertex $$$3$$$: symmetric to vertex $$$1$$$, contribution $$$1$$$.
Averaging over the three starting vertices gives $$$\frac{1+2+1}{3} = \frac{4}{3}$$$.
Converting to modulo $$$10^9+7$$$: $$$3^{-1}=333333336$$$, hence $$$\frac{4}{3} \bmod 10^9+7 = 4 \cdot 333333336 \bmod 10^9+7 = 333333337$$$.
Farouk was bored, and so to relieve his boredom, he decided to play a game with a permutation. He wrote down a permutation $$$p_1, p_2, \cdots, p_n$$$ of the integers $$$0, 1, 2, \cdots, n-1$$$, and he wanted to find the sum of the MEX (Minimum Excluded Value$$$^{\text{∗}}$$$) over all subarrays. More formally, find $$$$$$ \sum_{1 \le l \le r \le n} \textbf{MEX}(\{ p_l, p_{l+1}, \cdots, p_{r-1}, p_r \}). $$$$$$ However, he found it rather tedious to calculate the sum of the MEX over all subarrays himself and so he tasked you with helping him.
$$$^{\text{∗}}$$$The MEX of a set of integers is the first nonnegative integer not in the set. For example, $$$\textbf{MEX}(\{ 2, 0, 1, 5 \}) = 3.$$$
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) – the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) – the length of the permutation.
The next line contains $$$n$$$ integers $$$p_1, p_2, ..., p_n$$$ ($$$0 \le p_i \le n-1$$$) – the elements of the permutation.
It is guaranteed that the the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer – the sum of the MEX over all subarrays of the permutation.
231 2 050 3 2 4 1
5 9
In the first test case, the MEX of $$$[0]$$$ and $$$[2, 0]$$$ is 1, the MEX of the entire permutation is 3, and the MEX of all other subarrays is 0. Thus the sum of MEX over all subarrays is $$$1 + 1 + 3 = 5$$$.
Meda loves solving number theory puzzles, I think you already know. So, he gives you this problem to solve it with him
He has an integer $$$n$$$ and an array $$$a$$$ of size $$$n$$$. He wants to know if there exists a non-empty subsequence of $$$a$$$ such that the sum of its elements is divisible by $$$n$$$.
Given an array $$$a = [a_1, a_2, \dots, a_n]$$$, a subsequence of $$$a$$$ is any sequence of the form
$$$$$$[a_{i_1}, a_{i_2}, \dots, a_{i_k}]$$$$$$
where $$$1 \leq i_1 \lt i_2 \lt \cdots \lt i_k \leq n$$$ and $$$k \geq 1$$$.
In other words, a subsequence is obtained by deleting zero or more elements from $$$a$$$ without changing the order of the remaining elements.
The first line of input contains a single integer $$$t$$$ $$$(1 \leq n \leq 10^5)$$$ — the size of the array.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ satisfying $$$1 \leq a_i \leq 10^5$$$ for all $$$1 \leq i \leq n$$$
Print "YES" if such a subsequence exists, otherwise print "NO".
3 1 4 2
YES
5 1 2 3 4 5
YES
In the first testcase, you can take the the first or the last element $$$1 + 2 \equiv 0 \pmod{3}$$$. You can also take the second and the last element $$$4 + 2 \equiv 0 \pmod{3}$$$
In the second testcase, you can easily take every element in the array.
The three authors of this contest were playing a game. They were given a large positive integer $$$n$$$, represented as a binary string. Together, they need to choose a positive integer $$$x$$$ such that $$$ \lfloor \log_2 x \rfloor \;\le\; \lfloor \log_2 n \rfloor,$$$ that is, the binary representation of $$$x$$$ contains at most as many bits as the binary representation of $$$n$$$.
However, each of them wants to apply a different operation on $$$n$$$ using $$$x$$$:
- Meda wants to compute $$$n + x$$$.
- Farouk wants to compute $$$n \mid x$$$, where $$$\mid$$$ denotes the bitwise OR operation$$$^{\text{∗}}$$$.
- Bald wants to compute $$$n \oplus x$$$, where $$$\oplus$$$ denotes the bitwise XOR operation$$$^{\text{†}}$$$.
$$$^{\text{∗}}$$$For an explanation of the bitwise OR operation, see the notes.
$$$^{\text{†}}$$$For an explanation of the bitwise XOR operation, see the notes.
The first line contains a single integer $$$m$$$ $$$(1 \leq m \leq 10^6)$$$ — the length of the binary string.
The second line contains the integer $$$n$$$, given as a binary string of length $$$m$$$. It is guaranteed that the string has no leading zeros.
Print a single integer — the number of positive integers $$$x$$$ satisfying the conditions, modulo $$$10^{9}+7$$$.
5 11010
3
Bitwise OR is a binary operation which is performed on each bit of two integers independently. It outputs 1 if and only if either of the input bits is 1, that is, $$$0 \mid 0 = 0, 0 \mid 1 = 1, 1 \mid 0 = 1, 1 \mid 1 = 1$$$. For example, $$$101_2 \mid 011_2 = 111_2$$$.
Bitwise XOR is a binary operation which is performed on each bit of two integers independently. It outputs 1 if and only if the input bits are different, that is, $$$0 \oplus 0 = 0, 0 \oplus 1 = 1, 1 \oplus 0 = 1, 1 \oplus 1 = 0$$$. For example, $$$101_2 \oplus 011_2 = 110_2$$$.