For several years, Homs University organized the Homs Collegiate Programming Contest (HCPC). This year, however, the contest was cancelled.
In HCPC $$$2025$$$, more than $$$100$$$ balloons were distributed during the contest. The judges now wonder, how many were distributed in HCPC $$$2026$$$?
The only line contains the string $$$\texttt{HCPC}$$$.
Print one integer: the number of balloons distributed in HCPC 2026.
HCPC
0
Because HCPC 2026 did not take place, no balloons were distributed in it.
This is an interactive problem.
There are $$$2N$$$ friends sitting around a circle, numbered from $$$1$$$ to $$$2N$$$ in clockwise order. For every $$$1 \le i \lt 2N$$$, friends $$$i$$$ and $$$i+1$$$ are adjacent, and friends $$$2N$$$ and $$$1$$$ are adjacent. For every $$$1 \le i \le N$$$, friends $$$i$$$ and $$$i+N$$$ sit opposite each other.
Friend $$$i$$$ has a hidden positive integer $$$a_i$$$. The hidden integers satisfy
$$$$$$|a_i-a_j|=1$$$$$$
for every pair of adjacent friends $$$i$$$ and $$$j$$$.
Your task is to find two opposite friends who have the same hidden integer, or determine that no such pair exists.
The hidden integers are fixed before the interaction starts and do not change in response to your queries.
The first line contains one integer $$$N$$$ ($$$2 \le N \le 10^5$$$).
It is guaranteed that $$$1 \le a_i \le 10^9$$$ for every $$$1 \le i \le 2N$$$, and that the hidden integers satisfy all conditions from the statement.
To learn the hidden integer of friend $$$i$$$ ($$$1 \le i \le 2N$$$), print
$$$$$$\mathtt{?\ i}$$$$$$
Then read one integer: the value of $$$a_i$$$.
You may make at most $$$40$$$ queries.
When you have found two opposite friends $$$i$$$ and $$$j$$$ with $$$a_i=a_j$$$, print
$$$$$$\mathtt{!\ i\ j}$$$$$$
You may print $$$i$$$ and $$$j$$$ in either order.
If no such pair exists, print
$$$$$$\mathtt{!\ -1\ -1}$$$$$$
The final answer does not count as a query. After printing the final answer, your program must terminate immediately.
After every query and after the final answer, print an end-of-line and flush the output buffer. Otherwise, you may receive the Idleness limit exceeded verdict.
If your program prints an invalid query, makes more than $$$40$$$ queries, or prints an incorrect final answer, it will receive a wrong answer verdict.
2 100 100
? 1 ? 3 ! 1 3
The sample shows one possible interaction. The values read after the two queries are both $$$100$$$, so friends $$$1$$$ and $$$3$$$ form a valid final answer. Empty lines are shown only to make the order of messages easier to read.
To flush the output buffer, use:
- cout « endl in C++;
- System.out.flush() in Java;
- flush=True in Python.
Unfortunately, the HCPC was cancelled only hours before the contest, by which time the T-shirts had already arrived. However, because everyone was fighting with everyone else at that moment, no one noticed their arrival except for one man: the big, big thief! He ran off with all the T-shirts, washed them, and put them on his clotheslines to dry.
There are $$$n$$$ horizontal clotheslines, numbered from $$$1$$$ to $$$n$$$ from top to bottom. Each clothesline initially holds exactly $$$m$$$ HCPC T-shirts. A T-shirt is described by its horizontal coordinate $$$x$$$. The coordinates of the T-shirts on the same clothesline are pairwise distinct.
When a T-shirt falls, every T-shirt with the same coordinate on a lower clothesline falls as well. All such T-shirts fall simultaneously. A fallen T-shirt is removed permanently. Fallen T-shirts remain absent in later queries.
Since the big, big thief stole those clotheslines a loooooooong time ago, some of them have begun to fall. You must process $$$q$$$ queries. In each query, clothesline $$$r$$$ falls, and every T-shirt still present on it falls too. The resulting cascade is then applied. No clothesline is queried more than once. For each query, find the number of T-shirts that fall during that query.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$, $$$n \cdot m \le 2 \cdot 10^5$$$) — the number of clotheslines and the initial number of T-shirts on each clothesline.
Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$x_{i,1},x_{i,2},\ldots,x_{i,m}$$$ ($$$1 \le x_{i,j} \le 10^9$$$), the coordinates of the T-shirts on clothesline $$$i$$$. The coordinates in each of these lines are pairwise distinct.
The next line contains an integer $$$q$$$ ($$$1 \le q \le n$$$) — the number of queries.
Each of the next $$$q$$$ lines contains an integer $$$r$$$ ($$$1 \le r \le n$$$), meaning that clothesline $$$r$$$ falls. All queried clotheslines in a test case are pairwise distinct.
It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For every query, print one integer — the number of T-shirts that fall during that query.
1 3 2 1 2 2 3 1 3 3 2 1 3
3 3 0
The following diagram illustrates the first query of the example. Each blue circle is a T-shirt, and its number is its horizontal coordinate. The red crosses mark the T-shirts that fall.
In the first query of the example, the two T-shirts on clothesline $$$2$$$ fall. The T-shirt at coordinate $$$3$$$ also makes the T-shirt at coordinate $$$3$$$ on clothesline $$$3$$$ fall, so the answer is $$$3$$$.
In the second query, both T-shirts on clothesline $$$1$$$ fall. They make the remaining T-shirt at coordinate $$$1$$$ on clothesline $$$3$$$ fall. The answer is again $$$3$$$.
Clothesline $$$2$$$ is already empty during the final query, so its answer is $$$0$$$.
After reading about vibe coding from a source he trusted(or used to trust), Radwan laid off all his engineers and hired vibe coders. Two months later, he found out how big his mistake was, so he wants to hire new engineers.
There are $$$n$$$ software engineers working for $$$m$$$ companies. The company of engineer $$$i$$$ is $$$c_i$$$, and hiring this engineer costs $$$s_i$$$. When Radwan pays the engineer $$$s_i$$$, he leaves his old company and joins Radwan's.
Radwan's company currently has no engineers. He wants to hire some of those engineers so that after the hiring is finished, his company has strictly more engineers than each of the other $$$m$$$ companies.
Find the minimum total hiring cost needed to achieve this goal.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 3000$$$) — the number of engineers and the number of other companies.
Each of the next $$$n$$$ lines contains two integers $$$c_i$$$ and $$$s_i$$$ ($$$1 \le c_i \le m$$$, $$$1 \le s_i \le 10^9$$$) — engineer $$$i$$$'s current company and hiring cost.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$3000$$$.
For each test case, print one integer — the minimum total cost required.
1 3 2 1 100 1 300 2 250
350
In the sample, he hires the engineer from company $$$1$$$ whose cost is $$$100$$$ and the engineer from company $$$2$$$ whose cost is $$$250$$$. His company then has $$$2$$$ engineers, while companies $$$1$$$ and $$$2$$$ have $$$1$$$ and $$$0$$$ engineers, respectively. The total cost is $$$100+250=350$$$.
There are $$$n$$$ horizontal rows of pins, numbered from $$$1$$$ to $$$n$$$ from top to bottom. Adjacent rows are one unit apart, and adjacent pins in the same row are one unit apart.
Row $$$i$$$ contains $$$a_i$$$ pins, where $$$a_1 \le a_2 \le \cdots \le a_n$$$. Its pins have coordinates $$$$$$ (0,i),(1,i),\ldots,(a_i-2,i),(a_i-1,i). $$$$$$ Thus, the leftmost pins of all rows lie on the same vertical line $$$x=0$$$, while longer rows extend farther to the right.
The following diagram shows the rows for $$$a=[1,2,4,4,7]$$$. The number written inside a pin is its horizontal coordinate. The orange square is one valid band of size $$$2$$$.
A rubber band of size $$$k$$$ is an axis-aligned square whose four vertices are pins at $$$$$$ (x,s),\quad(x+k-1,s),\quad(x,s+k-1),\quad(x+k-1,s+k-1) $$$$$$ for some integers $$$s$$$, $$$x$$$, and $$$k\ge1$$$. A band of size $$$1$$$ consists of a single pin. A pin is covered if it lies inside at least one band, and rubber bands may overlap.
Find the minimum number of rubber bands required to cover every pin.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of rows.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers of pins in the rows.
It is guaranteed that $$$a_1 \le a_2 \le \cdots \le a_n$$$ and that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print one integer — the minimum number of rubber bands required to cover every pin.
6 1 4 2 2 2 3 1 3 3 4 3 4 5 5 3 2 8 8 5 1 2 4 6 8
4 1 3 4 5 7
In the first test case, there is only one row, so every pin requires its own size-$$$1$$$ band.
In the second test case, one size-$$$2$$$ band covers all four pins.
After Najjar travelled from Aleppo to take part in HCPC, it was cancelled. But he decided to stay in Homs, hoping the HCPC will happen. He waited for hours, days, weeks, months and years, but the HCPC didn't happen. Since a regular clock could not measure such a long wait, his teammate Mohannad gave him a magic clock.
Mohannad's magic clock has $$$n$$$ hands, numbered from $$$1$$$ to $$$n$$$. At time $$$0$$$, every hand starts a new cycle.
Hand $$$1$$$ is the fastest hand and needs exactly $$$x$$$ seconds to complete one full cycle.
For each $$$i$$$ from $$$2$$$ to $$$n$$$, one full cycle of hand $$$i$$$ takes as much time as $$$a_i$$$ full cycles of hand $$$i-1$$$.
The rumors say the HCPC will be held after $$$y$$$ seconds. For each hand, determine the number of full cycles it completes during those $$$y$$$ seconds. A cycle completed exactly at time $$$y$$$ is counted.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le x,y \le 10^{18}$$$) — the number of hands, the duration of one cycle of hand $$$1$$$, and the observed amount of time, respectively.
The second line of the test case contains $$$n-1$$$ integers $$$a_2,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$, where $$$c_i$$$ is the number of full cycles completed by hand $$$i$$$ during the first $$$y$$$ seconds.
52 3 1023 2 255 105 1 1002 5 2 54 10 91 1 14 6 3603 4 5
3 112 2 0100 50 10 5 10 0 0 060 20 5 1
In the second test case, the first hand needs $$$2$$$ seconds to complete a cycle. For the second hand, the first one needs to complete $$$5$$$ cycles so the second completes one cycle. And the second hand completes $$$10$$$ cycles so the third completes one cycle.
In the fourth test case, even the fastest hand cannot complete a cycle within the first $$$9$$$ seconds.
Ahmad has expanded his repertoire from strings to bits! Naturally, he only knows one spell: transforming an integer $$$x$$$ into $$$F(x)$$$.
The function $$$F(x)$$$ changes the rightmost zero (the least significant unset bit) in the binary representation of $$$x$$$ into a $$$1$$$.
For example:
- $$$F(5) = F(101_2) = 111_2 = 7$$$
- $$$F(7) = F(0111_2) = 1111_2 = 15$$$
- $$$F(0) = F(0_2) = 1_2 = 1$$$
- $$$F(2) = F(10_2) = 11_2 = 3$$$
You are given two positive integers $$$a$$$ and $$$b$$$. In a single operation, you may apply Ahmad's spell to either $$$a$$$ or $$$b$$$, replacing the chosen number with $$$F(a)$$$ or $$$F(b)$$$, respectively. You may perform this operation as many times as you like.
Find the minimum total number of spells required to make $$$a = b$$$.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each of the next $$$t$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a,b \le 10^{18}$$$).
For each test case, output one integer — the minimum number of moves required to make $$$a=b$$$.
65 742 424 81 210 1215 16
106245
you already know who made this problem right ;)
You are given an undirected graph with $$$n+2$$$ vertices. The ordinary vertices are numbered from $$$1$$$ to $$$n$$$, and the two special vertices are called $$$x$$$ and $$$y$$$.
There are no edges between two ordinary vertices, and there is no edge between $$$x$$$ and $$$y$$$. The edges incident to the special vertices are described by two binary strings $$$a_x$$$ and $$$a_y$$$:
- vertex $$$i$$$ is adjacent to $$$x$$$ if and only if $$$a_x[i]=\texttt{1}$$$;
- vertex $$$i$$$ is adjacent to $$$y$$$ if and only if $$$a_y[i]=\texttt{1}$$$.
A walk of length $$$k$$$ is a sequence of vertices $$$w_0,w_1,\ldots,w_k$$$ such that every two consecutive vertices are connected by an edge. Vertices and edges may occur more than once in a walk.
You must answer $$$q$$$ queries. In a query, you are given two ordinary vertices $$$u$$$ and $$$v$$$, and an integer $$$k$$$. Find the number of different walks of length exactly $$$k$$$ that start at $$$u$$$ and finish at $$$v$$$.
And as the author of this problem is always kinda tired (even though he is the first Node bender), you got to do this mission.
Because the answer can be large, print it modulo $$$10^9+7$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^5$$$) — the number of ordinary vertices and the number of queries.
The second line contains a binary string $$$a_x$$$ of length $$$n$$$. Its $$$i$$$-th character is $$$\texttt{1}$$$ if and only if vertex $$$i$$$ is adjacent to $$$x$$$.
The third line contains a binary string $$$a_y$$$ of length $$$n$$$. Its $$$i$$$-th character is $$$\texttt{1}$$$ if and only if vertex $$$i$$$ is adjacent to $$$y$$$.
Each of the next $$$q$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$k$$$ ($$$1 \le u,v \le n$$$, $$$1 \le k \le 10^5$$$) — the starting vertex, the finishing vertex, and the required length of the walk.
For each query, print one integer — the number of walks satisfying the query, modulo $$$10^9+7$$$.
3 5 110 011 1 1 1 1 1 2 1 2 2 2 2 2 2 1 4
0 1 1 2 3
In the example, vertex $$$1$$$ is adjacent only to $$$x$$$, vertex $$$2$$$ is adjacent to both $$$x$$$ and $$$y$$$, and vertex $$$3$$$ is adjacent only to $$$y$$$.
For the query $$$u=2$$$, $$$v=2$$$, $$$k=2$$$, the two walks are $$$$$$ 2\to x\to2 \qquad\text{and}\qquad 2\to y\to2. $$$$$$
For the query $$$u=2$$$, $$$v=1$$$, $$$k=4$$$, the three walks are $$$$$$ 2\to x\to1\to x\to1, $$$$$$ $$$$$$ 2\to x\to2\to x\to1, $$$$$$ and $$$$$$ 2\to y\to2\to x\to1. $$$$$$
Ahmad, the legendary (and slightly unhinged) String Bender, has decided to torture his innocent strings once again!
You are given two non-empty strings $$$s$$$ and $$$t$$$, both consisting of lowercase English letters, and an integer $$$k$$$.
In a single operation, you may insert any lowercase English letter at any position in $$$s$$$—before its first character, after its last character, or between any two adjacent characters. You must perform exactly $$$k$$$ operations, resulting in a string of length $$$|s| + k$$$.
An occurrence of $$$t$$$ is defined as a contiguous substring equal to $$$t$$$. Overlapping occurrences are allowed and counted independently.
Find the maximum possible number of occurrences of $$$t$$$ in the modified string after performing exactly $$$k$$$ insertions.
The first line contains the string $$$s$$$ ($$$1 \le |s| \le 10$$$).
The second line contains the string $$$t$$$ ($$$1 \le |t| \le 10$$$).
The third line contains an integer $$$k$$$ ($$$0 \le k \le 10^7$$$).
Both strings consist only of lowercase English letters.
Print one integer — the maximum possible number of occurrences of $$$t$$$ after inserting exactly $$$k$$$ characters into $$$s$$$.
aa aa 2
3
b ab 3
2
abc bc 0
1
spongebobstringbend1000
100
In the first example, insert two letters to obtain aaaa. The string aa occurs starting at positions $$$1$$$, $$$2$$$, and $$$3$$$. These occurrences overlap.
In the second example, it is possible to obtain abab. The string ab then occurs twice.
After waiting a long time for HCPC, Najjar began dreaming about it. One of his nightmares went as follows:
Najjar wants to type a target string $$$s$$$ from left to right. Normally, pressing a letter's key appends one copy of that letter to the text.
Because it is a dream, Najjar may choose at most one lowercase English letter and apply magic to its key. If he chooses a letter $$$c$$$, then every press of the $$$c$$$ key appends exactly two consecutive copies of $$$c$$$ instead of one. The magic cannot be disabled and is applied before he starts typing. All other keys continue to append one letter per press.
Najjar must obtain exactly $$$s$$$. What is the minimum number of key presses he needs?
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each test case consists of one string $$$s$$$ ($$$1 \le |s| \le 2\cdot 10^5$$$) containing only lowercase English letters.
The sum of $$$|s|$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, print one integer — the minimum number of key presses required to type $$$s$$$ exactly.
7 a aa aba aabbaa aaabbb aabbcc aaaaaa
1 1 3 4 6 5 3
There is a grid of $$$n \times n$$$ rooms. Rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Room $$$(i,j)$$$ lies in row $$$i$$$ and column $$$j$$$.
There are $$$2n$$$ fans. For each row $$$i$$$, there is a row fan that cools every room in row $$$i$$$ when it is switched on. Switching on this fan costs $$$r_i$$$. For each column $$$j$$$, there is a column fan that cools every room in column $$$j$$$ when it is switched on. Switching on this fan costs $$$c_j$$$.
You may switch on any subset of the fans, paying the sum of their costs. A room is cooled if at least one of its row fan and its column fan is switched on.
Yazan starts in room $$$(1,1)$$$ and wants to reach room $$$(n,n)$$$. In one move, he may go to a room that shares a side with his current room. Every room in his path, including $$$(1,1)$$$ and $$$(n,n)$$$, must be cooled.
Find the minimum total cost of switching on fans so that such a path exists.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of rows and columns.
The second line of each test case contains $$$n$$$ integers $$$r_1,r_2,\ldots,r_n$$$ ($$$1 \le r_i \le 10^9$$$) — the costs of the row fans.
The third line of each test case contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le 10^9$$$) — the costs of the column fans.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one integer — the minimum total cost required to create a cooled path from $$$(1,1)$$$ to $$$(n,n)$$$.
3 3 1 100 100 100 100 1 3 3 100 4 100 2 100 3 100 2 100 3 100 4
2 9 9
In the first sample, switching on the fan of row $$$1$$$ and the fan of column $$$3$$$ costs $$$1+1=2$$$. The diagram in the statement shows the cooled rooms and one possible path from $$$(1,1)$$$ to $$$(3,3)$$$.
We call an ordered pair of positive integers $$$(x,z)$$$ beautiful if there exists an integer $$$y$$$ such that [ x < y < z, ] $$$x$$$ divides $$$y$$$, and $$$y$$$ divides $$$z$$$.
The integer $$$y$$$ may be any integer; it does not have to occur in the array.
You are given several arrays. For each array, count the number of ordered pairs of indices $$$(i,j)$$$ such that $$$i \ne j$$$ and $$$(a_i,a_j)$$$ is beautiful.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the array.
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^6$$$.
For each test case, print one integer — the number of ordered pairs of indices $$$(i,j)$$$ such that $$$i \ne j$$$ and $$$(a_i,a_j)$$$ is beautiful.
3 8 1 2 3 4 6 8 4 8 2 2 2 5 1 4 1 4 4
7 0 6
In the first test case, the beautiful ordered pairs of values, with repetitions listed only once, are [ (1,4), (1,6), (1,8), (2,8). ] The values $$$4$$$ and $$$8$$$ each occur twice. Consequently, these value pairs correspond to $$$2+1+2+2=7$$$ ordered pairs of indices.
For example, $$$(2,8)$$$ is beautiful: we may choose $$$y=4$$$, because $$$2 \lt 4 \lt 8$$$, $$$2$$$ divides $$$4$$$, and $$$4$$$ divides $$$8$$$.
In the second test case, all values are equal, so the strict inequality in the definition can never hold.
In the third test case, every occurrence of $$$1$$$ can be paired with every occurrence of $$$4$$$. This gives $$$2\cdot3=6$$$ beautiful ordered pairs of indices.
There are infinitely many bulbs, numbered $$$1,2,3,\ldots$$$, and a sink numbered $$$0$$$.
Alice and Bob play a game. Alice moves first. On each turn, the player:
- chooses a glowing bulb $$$x$$$;
- chooses an integer $$$y$$$ such that $$$0\le y \lt x$$$;
- turns bulb $$$x$$$ off;
- if $$$y \gt 0$$$, toggles bulb $$$y$$$: an off bulb turns on, and a glowing bulb turns off.
If $$$y=0$$$, nothing is toggled. A player who has no glowing bulb to choose loses.
You are given an array $$$a$$$ and $$$q$$$ queries. Each query $$$[l,r]$$$ starts an independent game. At the start of that game, bulb $$$x$$$ is glowing if and only if $$$x$$$ appears at least once in [ a_l,a_{l+1},...,a_r. ] Repeated occurrences of the same value still light only one bulb.
For every query, determine the winner if both players play optimally.
The first line contains an integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.
For each test case:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le 2\cdot 10^5$$$) — the array length and the number of queries.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$).
Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\le l\le r\le n$$$), describing one query.
The sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$. The sum of $$$q$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each query, print Alice if Alice wins; otherwise, print Bob.
1 5 5 1 2 1 3 2 1 1 1 3 1 5 2 4 3 3
Alice Alice Bob Bob Alice
After every exam, Nadeem and his friends have the same discussion: should they eat manaeesh at Alsyoufi or Caesar?
To settle the debate, they compare the two restaurants using three criteria:
- Distance: the restaurant with the smaller distance receives one point.
- Food quality: the restaurant with the larger food-quality score receives one point.
- Price: the restaurant with the smaller price receives one point.
For each criterion, the two values are different. Thus, exactly one restaurant receives a point from each criterion. The restaurant with more points wins.
Determine the winning restaurant.
The first line contains three integers $$$D_1$$$, $$$Q_1$$$, and $$$P_1$$$ — the distance, food-quality score, and price of Alsyoufi, respectively.
The second line contains three integers $$$D_2$$$, $$$Q_2$$$, and $$$P_2$$$ — the distance, food-quality score, and price of Caesar, respectively.
Each of the six integers is between $$$1$$$ and $$$10^9$$$, inclusive.
It is guaranteed that $$$D_1$$$ and $$$D_2$$$ are different, $$$Q_1$$$ and $$$Q_2$$$ are different, and $$$P_1$$$ and $$$P_2$$$ are different.
Print Alsyoufi if Alsyoufi receives more points. Otherwise, print Caesar.
10 8 30 15 7 25
Alsyoufi
20 9 50 10 8 40
Caesar
1 1000000000 1 1000000000 1 1000000000
Alsyoufi
In the first example, Alsyoufi receives the points for distance and food quality, while Caesar receives the point for price. Therefore, Alsyoufi wins by $$$2$$$ points to $$$1$$$.
In the second example, Caesar receives the points for distance and price, while Alsyoufi receives the point for food quality. Therefore, Caesar wins by $$$2$$$ points to $$$1$$$.
In the third example, Alsyoufi receives all three points.