Given a positive integer $$$n$$$, you need to find out the minimum integer $$$k$$$ such that for any subset $$$T$$$ of the set $$$\{1,2,\cdots,n\}$$$ of size $$$k$$$, there exist two different integers $$$u,v \in T$$$ that $$$u$$$ is a factor of $$$v$$$.
The first line contains an integer $$$T~(1\le T\le 10^5)$$$ indicating the number of test cases.
Each of the following $$$T$$$ lines contains an integer $$$n~(2\le n\le 10^9)$$$ describing a test case.
For each test case, output a line containing an integer which indicates the answer.
4 2 3 4 5
2 3 3 4
Sunday morning has come, and all the autumn would be bright and cool, and brimming with life. There was a song in every heart, and if the heart was young the music issued at the lips. There was cheer in every face and a whoop in every step. Tom appeared on the sidewalk with a bucket of whitewash and a long-handled brush. He surveyed the stone chessboard in the park, and all gladness left him and a deep melancholy settled down upon his spirit. A giant chessboard, that is $$$n$$$ feet long and $$$m$$$ feet wide. Life to him seemed hollow, and existence but a burden.
Sighing, he dipped his brush with a little whitewash and thought how to start. He knew that he would select a starting point, which should be an arbitrary block in the chessboard. He would whitewash the block and move to an adjacent one; repeat the operation and finish his work in any place when the whole chessboard has been whitewashed. His footprints would defile a painted region even if he took off his shoes. So avoiding to go back to a completed block would be a wise choice.
But Tom's energy did not last. He began to think of the fun he had planned for this day, and his sorrows multiplied. Soon the free boys and girls would come tripping along the Yan Lake inside Nanjing University of Aeronautics and Astronautics Jiangning campus, and they would have the chance to take part in the ICPC contest facing interesting algorithms problems. Staring at the chessboard, a sudden curiosity urged him to pay attention to, between any two painted blocks, the shortest paths only passing painted blocks in which adjacent blocks should share a common edge.
"Damn it! The shortest distances may vary. I have to stop such a thing happening."
He quickly imagined a strategy that the shortest distance between any two blocks would remain unchanged after they were painted, and it would be a satisfactory beginning:
and another strategy not to be considered:
Now he wants to know how many different satisfactory strategies are there that can whitewash the whole chessboard. Can you help him?
The first line contains an integer $$$T~(1\le T\le 10^5)$$$ indicating the number of test cases.
For each test case, a single line containing two integers $$$n$$$ and $$$m~(1\le n, m\le 10^6)$$$ describes the size of the chessboard.
For each test case, output the number of different satisfactory strategies modulo $$$(10^9+7)$$$.
4 1 3 3 2 3 3 4 4
2 12 24 80
Zhe the bully, is condemned by all kinds of evil, like bullying those who are weaker. His teammates have been mistreated for a long time. Finally, they decided not to put up with their buddy any more and flee to Digital Village, with the bully in hot pursuit. Due to difficult terrain and a considerable amount of Digital Paths staggered, they can't be easily arrested.
Getting familiar with the terrain as soon as possible is important for these innocents to escape the threat of bullying. All they need now is to count the number of Digital Paths in Digital Village.
To simplify the problem, Digital Village is abstracted into a grid with $$$n$$$ rows and $$$m$$$ columns filled by integers. A Digital Path is a continuous walk in the grid satisfying the following conditions:
Here we have some examples.

Figure 1: An invalid path.

Figure 2: An invalid path.

Figure 3: An invalid path.

Figure 4: An invalid path.

Figure 5: All valid paths.
Digital Paths may partially overlap. In Figure 5, there are $$$4$$$ Digital Paths marked by different colours.
The first line contains two positive integers $$$n$$$ and $$$m~(1\le n,m\le 1\,000)$$$ describing the size of the grid.
Each of the next $$$n$$$ lines contains $$$m$$$ integers, the $$$j$$$-th of which, denoted by $$$a_{i,j}~(-10^7\le a_{i,j}\le 10^7)$$$, represents the value of the box in the $$$i$$$-th row and the $$$j$$$-th column.
Output the number of Digital Paths modulo $$$(10^9+7)$$$.
3 5 1 2 3 8 7 -1 -1 4 5 6 1 2 3 8 7
4
4 4 1 2 3 4 2 3 4 3 3 4 3 2 4 3 2 1
16
Given an $$$n\times n$$$ chessboard, the rows and columns are numbered from $$$1$$$ to $$$n$$$ respectively. RDC, a handsome juvenile, punched several holes in specified locations, the $$$i$$$-th of which locates at $$$(x_i,y_i)$$$.
RDC also has a pet Pork Ribs dragon whose name is PRD. Now, PRD is drunk and was left on the chessboard at the cell $$$(r,c)$$$. It will walk randomly and move to an adjacent cell every second with equal probability. Here two cells are adjacent if they share a common edge. PRD will fall into the hole and start to sleep when it arrives at a cell with a punched hole.
Now, RDC wonders the expected time consumption of his pet for each hole that his pet will finally stay in.
The first line contains an integer $$$T~(1\leq T\leq 20)$$$, indicating the number of test cases.
For each test case, the first line contains two integers $$$n$$$ and $$$k~(2\leq n\leq 200,1\leq k\leq 200)$$$ indicating the size of the given chessboard and the number of holes. Then $$$k$$$ lines follow, the $$$i$$$-th of which contains two integers $$$x_i$$$ and $$$y_i~(1\leq x_i,y_i\leq n)$$$ indicating the location of the $$$i$$$-th hole. The last line of each test case contains two integers $$$r$$$ and $$$c~(1\leq r,c\leq n)$$$ described as above.
We guarantee that PRD is not locating at a hole initially, and all given holes are distinct. We also guarantees that $$$\max(n,k) \gt 5$$$ hold in at most one test case.
For each test case, output the expected time consumption (in seconds) for each hole in order in a single line.
More precisely, if a hole is reachable and the reduced fraction of the expected time consumption is $$$\frac{p}{q}$$$, you should output the minimum non-negative integer $$$r$$$ such that $$$q \cdot r \equiv p \pmod{10^9+7}$$$. You may safely assume that such $$$r$$$ always exists in all test cases. If a hole is unreachable, output "GG" (without quotes) at the right place.
2 3 3 1 1 1 2 2 1 2 2 5 3 5 3 4 1 3 2 4 5
GG 4 4 669185882 381533358 341349117
As an astronomer, Alice pilots her spaceship to observe an unknown object in the universe. This object can be viewed as a point in the space in a common theoretical model since its size is significantly smaller than the viewing distance.
Building a space rectangular coordinate system centred at the object, a possible perfect observing position is such which locals at an integral point. Alice records the number of perfect observing positions whose viewing distances are equal to $$$d\in \mathbb{Z}$$$ as $$$f_d$$$.
Now, given a permitted range $$$[L,R]$$$ of viewing distance, a test coefficient $$$K$$$ and a large prime number $$$P$$$, you are asked to calculate $$$\Big(\sum\limits_{d=L}^{R} (f_d\text{ xor } K)\Big)\pmod{P}$$$ to explore the risk factor.
The first line contains an integer $$$T~(1\le T\le 10)$$$ representing the number of test cases.
For each test case, an only line contains four integers $$$L, R, K$$$ and $$$P$$$ described as above, where $$$0\le L\le R\le 10^{13}, 0\le K\le 10^{18}$$$, the prime number $$$P$$$ satisfies $$$P\le 3\times 10^{13}$$$ and $$$R-L+1\le 10^6$$$.
For each test case, print a line which contains an integer representing the risk factor inquired.
2 1 1 0 11 1 1 1 11
6 7
The story is purely fictitious.
Nearly all the students in No.84 University are asked to take a compulsory course called JL and pass the exam, which says that hundreds of students will take part in this final exam together. The teacher organizing the course is always trying to find a more efficient and fair way to grade students' test papers. In this year, you are appointed to write a program to grade papers.
Now you are given the Book of Requirement which is a dictionary consists of $$$n$$$ strings in lowercase letters, denoted by $$$s_1,s_2,\cdots,s_n$$$ in order. However, the book as a magic item may be modified with exchanges. It is possible to swap the positions of two strings inside the dictionary at any time. For instance, if one swap the first and the fifth strings, the so-called first string in this dictionary after the modification would be the fifth one originally.
The scoring criterion is given as follow. A student and his/her test paper are described as a string $$$q$$$ in lowercase letters together with three integral coefficients $$$k,l$$$ and $$$r$$$. The student's final score should be the number of strings $$$s_i$$$ in the Book of Requirement with $$$l\le i\le r$$$ such that the longest common prefix of $$$q$$$ and $$$s_i$$$ is of length at least $$$k$$$.
The first line contains two integers $$$n$$$ and $$$m~(1\leq n,m \leq 2\times 10^5)$$$ where $$$n$$$ is the number of strings in the Book of Requirement and $$$m$$$ is the total number of modifications and students.
The following $$$n$$$ lines are $$$n$$$ non-empty strings $$$s_1,s_2,\cdots,s_n$$$ indicating all string in the book, whose total length is up to $$$2\times 10^5$$$.
Then the following $$$m$$$ lines describe all modifications and students that are asked to grade in time sequence. Each line of them starts with an integer $$$opt~(1\leq opt\leq 2)$$$. If $$$opt=1$$$, it follows two integers $$$i$$$ and $$$j$$$ describing a modification to swap the $$$i$$$-th and the $$$j$$$-th string in the book, where $$$1\leq i,j\leq n$$$ and $$$i$$$ can be equal to $$$j$$$. If $$$opt=2$$$, it follows a non-empty string $$$q$$$ and three non-negative integers $$$k,l$$$ and $$$r$$$, where $$$0\leq k\leq |q|$$$ and $$$1\leq l \leq r \leq n$$$, representing a student as above.
It is guaranteed that the total length of $$$q$$$ provided in the input is up to $$$2\times 10^5$$$.
For each student, output a single line containing the score of his/her test paper.
3 4 aaa bbb aac 2 aasdd 2 1 3 2 aab 1 1 2 1 2 3 2 aat 2 1 2
2 1 2
In the example, the initial Book of Requirement consists of $$$s_1$$$=aaa, $$$s_2$$$=bbb and $$$s_3$$$=aac. For the first given student with the string $$$q$$$=aasdd, the longest common prefixes with aaa and aac are of length at least $$$2$$$. Hence his final score is $$$2$$$. For the second student, the only available string to consider in the book is the first one $$$s_1$$$=aaa.
Then a modification comes, and strings in the Book of Requirement become $$$s_1$$$=aaa,$$$s_2$$$=aac and $$$s_3$$$=bbb. For the third student, both $$$s_1$$$ and $$$s_2$$$ have a common prefix with given $$$q$$$=aat of length $$$2$$$. Hence the answer is $$$2$$$.
Five desperados are playing a poker game.
The hot dealer Myla organizes a $$$n$$$-round competition. Before the game, each player has $$$100$$$ pots corresponding to a certain amount of money. A penniless player, whose pot is zero, will be disqualified and is not allowed to play anymore.
As in most poker games, the deck is a standard $$$52$$$-card deck containing no jokers. Instead of a fair shuffle of the cards, Myla has decided the order of cards on ahead of time.
Now the game begins.
During every round, play begins with each player being dealt two private cards face down, with the first non-disqualified player receiving the first and the second cards, and the second non-disqualified player receiving the third and fourth cards, and etcetera. These cards are the players' hole cards.
The hand begins with a pre-flop betting round in which all players make decisions one by one in order. Each player may fold, which is to drop out of the hand and give up in this round, or call, which is to call for a bet of $$$5$$$ pots.
After the pre-flop betting round, the hot dealer Myla deals a flop: three face-up community cards. The flop is followed by a second betting round similarly. Each player may fold, which is to drop out of the hand losing any bets they have already made, or call, which is to call for a bet of $$$5$$$ pots.
After the flop betting round ends, two more community cards are dealt, followed by a third betting round as before.
If a player wants to remain after the final betting round, he must call for $$$15$$$ pots in total. But there is one exception. If a player, before the pre-flop betting round, has less than $$$15$$$ pots, he is not allowed to take part in even the pre-flop betting round unless he declares himself all in in the pre-flop betting round betting his entire stack. If a player goes all-in, he does not need to bet anymore and will be remained after the final betting round no matter whether he would be willing or not.
At any time during a round, if only one player remains and all other players have folded, the remaining player is awarded the pot and is not required to show his hole cards. If two or more players remain after the final betting round, a showdown occurs. On the showdown, each player plays the best poker hand they can make from the seven cards comprising their two-hole cards and the five community cards.
The player who has the best hand takes all the pots called in betting rounds. If the best hand is shared by more than one player, then one in the last order takes all the pots.
Following list shows the possible hand values in increasing order.
The card's numerical rank is also important. The card rank with highest first is given by A K Q J T 9 8 7 6 5 4 3 2 (A, only in the case of Straight A2345).
If several players share a common hand value, the rank of the critical card higher, the hand better. In a HighCard, the critical card is the one with the highest rank. In a Pair, the critical card is the one appearing in a pair with the highest rank. If the hand is Three of a kind, the card in the triple is critical. The card with the highest rank in a Straight or a Flush is the critical card, but note that 5 is the critical card in Straight A2345 but Ace is the critical one in Straight TJQKA. Please pay attention to this case and note that if cards in A2345 are of the same suit, it should be regarded as Flush or the so-called Straight Flush, and the critical card here is the Ace.
Now, let's talk about these desperados. All of them were professional ICPC competitors and they all know how to design a good strategy.
The first one is John-zeng Montagu. If his pot is less than $$$15$$$, he folds in the very beginning. He calls in the pre-flop betting round only if his hole cards are of the same suit. He always calls in the flop betting round and calls in the third betting round if the best poker hand he can make is not worse than Pair.
The second player is Brain-chen Molony. In the pre-flop betting round, he calls or even goes all-in if he has at least $$$15$$$ pots or his hole cards are the double Aces. He calls in the flop betting round if the given $$$5$$$ cards are not worse than Pair, or he can make it Straight or Flush with one more ideal card. He calls in the third betting round unless there are at least four community cards with the same suit.
The third player is Wild-tang-Bill Hickok. He calls or even goes all-in, in the pre-flop betting round, if he holds at least one Ace or the value difference between his hole cards is less than three. In the flop betting round, he folds when two of the community cards share the same value but the value does not appear in his hole cards. He always calls in the third betting round.
The fourth player is Kerry-wu Packer. In the pre-flop betting round, he calls or even goes all-in if he holds a card whose rank is higher than Jack (including Ace). He calls in the flop betting round if he holds a card higher than all community cards, or he can pair a hole card up with the highest community card. In the third betting round, he calls if the best hand is not worse than Three of a kind, or at least Pair and the rank (of the Pair) is higher than the rank of the third-highest community card (counted with multiplicity).
The last player is Archie-zou Karas. In the pre-flop betting round, he calls or even goes all-in only if there is only one another player called. Then he always calls in the second and the third round.
The first line contains an integer $$$n~(1\le n\le 1\,000)$$$ indicating the total number of rounds organized.
Each of the following $$$n$$$ lines contains $$$15$$$ integers describing all cards dealt by the hot dealer Myla in order. Note that the hot dealer can deal less than fifteen cards and remain some in her hand since some players may be disqualified. The numbers from $$$1$$$ to $$$13$$$, from $$$14$$$ to $$$26$$$, from $$$27$$$ to $$$39$$$ and from $$$40$$$ to $$$52$$$ correspond to cards in different suits from Ace, 2 to 10, Jack, Queen and King.
Output five lines, each of which contains a number indicating the final pot of the corresponding player.
2 1 2 8 10 3 11 15 12 14 27 42 43 45 48 13 14 2 8 10 3 11 5 23 1 27 42 43 13 45 48
90 90 100 115 105
5 9 5 19 35 30 42 18 8 21 51 16 26 32 29 49 17 50 13 7 37 21 25 31 28 18 30 27 24 16 15 31 38 52 46 1 29 41 12 39 24 10 45 13 22 42 8 10 33 18 39 49 29 43 51 2 35 19 27 41 12 48 13 33 39 30 47 32 24 12 9 42 1 18 41 51
65 115 115 100 105
5 51 31 17 50 24 15 25 20 22 16 44 6 19 39 28 34 1 21 10 31 15 35 8 27 51 32 23 48 24 29 39 18 27 14 31 2 35 51 44 21 24 6 43 16 19 9 44 4 19 35 47 15 51 25 20 40 8 21 6 7 49 35 11 12 44 29 22 9 16 13 4 17 32 25 7
100 125 115 75 85
5 16 41 30 6 5 39 22 1 29 42 32 49 40 27 21 39 14 32 48 6 37 23 35 13 52 43 2 24 38 45 49 42 38 18 47 52 30 15 16 1 26 31 28 6 40 47 31 22 45 49 46 36 17 35 48 38 33 13 16 20 41 17 9 34 25 21 8 18 22 24 4 20 26 15 42
90 80 100 115 115
5 26 38 46 4 52 15 51 7 1 30 5 3 33 47 34 22 7 15 9 5 29 32 23 30 25 33 2 1 50 4 22 44 31 33 32 39 26 5 21 15 48 2 52 37 13 21 50 12 7 43 26 32 28 42 30 20 9 35 47 8 38 12 4 33 10 25 50 37 46 36 6 40 29 48 5
100 65 100 120 115
5 32 51 43 23 30 17 36 37 48 22 46 41 20 1 42 49 29 40 4 19 46 13 39 8 12 47 38 16 32 34 37 34 45 36 10 26 33 21 46 35 39 13 41 27 19 51 15 42 35 27 52 18 1 44 37 26 39 33 32 8 31 50 52 24 37 17 26 2 20 13 1 38 9 49 51
85 105 110 100 100
Prince Mochi of the Mochi Kingdom falls in love with Princess Tofu of the Tofu Kingdom, but the queen of the Tofu Kingdom does not assent to this marriage.
The queen challenges their love and advocates a task for Prince Mochi. Solving this task is the premise for earning their happiness. The lack of capacity obliges Prince Mochi to ask you for help.
Here is the task: Princess Tofu, King Tofu, the queen, the minister, maids, chefs, and many others are all together for the task, all staying in separate rooms. Note that there is no empty room. Each one of them knows where he/she is and where any other people are.
Prince Mochi is asked to find the princess. He can inquire anyone about the following three types of questions:
They will never refuse to answer the questions, but may not tell the truth. People, including Princess Tofu herself, who support this marriage will present the facts. The opposition, like the queen, will always provide an incorrect answer. Other participants will be arbitrary.
Prince Mochi does not want to spend too much time and so he will query as little as possible. Can you tell him the minimum number of questions he really needs to confirm where his darling is under any circumstances? But sometimes, the task is impossible, then you should also remind him to begin a new love affair.
The only line in input contains three integers $$$a~(1 \le a \le 2 \times 10^5)$$$, $$$b$$$ and $$$c~(0 \le b,c \le 2 \times 10^5)$$$ which represent the number of participants who support this marriage, who are against this marriage and who do not really care about it respectively.
If it is impossible to determine where Prince Mochi is, output "NO" (without quotes). Otherwise, output "YES" (without quotes) at first following an integer indicating the minimum number of questions the prince needs to inquire in the second line.
2 0 0
YES 1
1 1 0
NO
In the second sample case, Prince Mochi may ask all available questions to both participants. However, in the case when they always provide the same answer, the prince cannot ensure where the princess is. Thus the answer is "NO".
There are $$$n+1$$$ space stations in Penguin Galaxy, numbered from $$$0$$$ to $$$n$$$. The $$$i$$$-th one has so-called energy of amount $$$a_i$$$.
When you arrive at a station, you can gain all the energy in this station. Now, you are staying at the $$$0$$$-th station, and you have already got the energy in this station of amount $$$a_0$$$. You will only be allowed to move to a station whose energy is less than or equal to what you've got at each time, and the movement between stations will cost you nothing, which can be ignored in computation.
Now, you decide to visit each station exactly once. How many different plans do you have to complete your trip? Since the answer will be pretty large, you just need to find the number module $$$10^9+7$$$.
The first line contains a single integer $$$n~(1\le n\le 10^5)$$$.
The second line contains $$$n+1$$$ integers $$$a_0,a_1,a_2,\cdots,a_n~(0\le a_i\le 50)$$$.
The output contains a single integer in a line indicating the number of different plans to complete your trip visiting all stations modulo $$$10^9+7$$$.
3 2 1 2 3
4
5 1 1 1 1 2 3
54
In the first example, the visiting order can be one of [0,1,2,3], [0,1,3,2], [0,2,1,3] and [0,2,3,1]. However, it cannot be [0,3,1,2] or [0,3,2,1]. Indeed when you start from the $$$0$$$-th station, you have gained only $$$2$$$ units of energy. Then you are not allowe to jump to the $$$3$$$-th statio since the energy there is $$$3$$$ which is bigger than what you hold.
Over time, those coaches in BDN Collegiate Progranuning Contest split into two camps. The big danger is that, while optimists and pessimists battle it out, the environment of this area becomes ever more divided between universities with outstanding student resources surrounded by a vast neglected group of stagnation.
Amy and Bob, as the linchpins of these two camps respectively, decided to put the end to the rival. Now both camps hold $$$n$$$ coders and $$$n$$$ tea-bringers as the last resource on hand. They will form teams in pair that each team should consist of a coder and a tea-bringer. The power of a team is regarded as the sum of powers of both members.
Now Bob hired a spy and has got some information about the plan of his rival: the power of each team which will present for the enemy camp, and the corresponding unit of reputations that Bob would gain after beating this team. Naturally, he hopes to make the best arrangement of teams in his camp for more reputations.
These two camps will have a collision soon, and their teams will fight one on one in random order. That is, we may have $$$n!$$$ different situations appearing in this collision. A team would triumphantly return if it has a higher power. When two teams of the same power meet, the one led by Amy would beat the rival by a neck.
Can you calculate the maximum expected unit of reputations that Bob will gain? To make the answer be an integer, you are asked to multiply the answer by $$$n$$$ and we guarantee that the expected number multiplied by $$$n$$$ should always be an integer.
The input contains five lines, and the first line is consist of an integer $$$n~(1\le n \le 400)$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n~(-10^{18}\leq a_i\leq 10^{18})$$$, indicating the powers of all the teams led by Amy.
The third line contains $$$n$$$ integers $$$p_1,p_2,\cdots,p_n~(1\leq p_i\leq 10\,000)$$$, indicating the corresponding units of reputations that Bob would gain if these teams led by Amy are beaten.
The fourth line contains $$$n$$$ integers $$$b_1,b_2,\cdots,b_n~(-10^{18}\leq b_i\leq 10^{18})$$$, indicating the powers of all coders in the camp of Bob.
The last line contains $$$n$$$ integers $$$c_1,c_2,\cdots,c_n~(-10^{18}\leq c_i\leq 10^{18})$$$, indicating the powers of all tea-bringers in the camp of Bob.
Output an integer in a single line indicating the maximum expected number of wins multiplied by $$$n$$$.
4 1 2 3 4 1 1 1 1 0 0 1 1 0 1 1 2
3
One day, ABC and DD found a triangular wheat field, and they decide to cut it into two pieces with the same area with a segment. Because of various reasons, one of the endpoints of the division line is fixed at $$$(p_x, p_y)$$$. Now you are asked to find the other endpoint of the segment.
If the given endpoint does not lie on the boundary of the wheat field, the problem should be regarded as invalid. The other endpoint required should also locate on the boundary.
The input provides several test cases and the first line of the input contains a single integer $$$T~(1 \le T \le 10^6)$$$ indicating the number of cases.
For each test case, eight integers $$$x_1,y_1,x_2,y_2,x_3,y_3,p_x$$$ and $$$p_y$$$ are given in a line, where $$$(x_1,y_1),(x_2,y_2)$$$ and $$$(x_3,y_3)$$$ describe the coordinates of vertices for the given triangle wheat field which are guaranteed to be not colinear, and $$$(p_x,p_y)$$$ is the given endpont of the segment. All coordinates are integers in the range $$$[0,10^5]$$$.
For each test case, output the coordinate of the other endpoint of the division segment, or output the number -1 if the problem, in this case, is invalid.
Formally, if your answer is $$$a$$$ and the jury's answer is $$$b$$$, then your answer will be considered correct if and only if $$$\frac{|a - b|}{\max\{1, |b|\}} \le 10^{-6}$$$.
2 0 0 1 1 1 0 1 0 0 0 1 1 1 0 2 0
0.500000000000 0.500000000000 -1