Chino has some special preferences toward string.
Now Chino has a string set with $$$m$$$ strings. She marks each string in the set with specific scores indicated the level of her favor. The special preferences of Chino toward string is when a string with positive score she will like it and with negative score she disgust.
Chino wants to build a new string with $$$n$$$ characters, then she want to score this string. The score of new string is calculated by the strings in the set is equal to the sum of each of them occurrences times in new string multiplied respective scores.
Now there is a sample case. In the set there is only contain one string "aaa" and scored 3 points. The new string is "aaaa". Then the string "aaa" occurs two times in the new string , so the new string should be scored 6 points.
Now Chino wants to know the maximal score of new string she built.
First input two integers $$$n,m(1 \leq n \leq 10^9,1 \leq m \leq 200)$$$ indicate the length of the new string need built and the size of the strings set.
Then input m strings named s with respective scores $$$v(-10^6 \leq v \leq 10^6)$$$.
Assure $$$ \sum \left | s \right | \leq 200 $$$ , $$$ \left | s \right | $$$ indcate the length of the string.
You just output one integer of the maximal score point.
17 3 helloworld 100 ldldl 5 aaa -6
115
The string with maximal score is "helloworldldldldl".
Mr. Cocktail like a game named Hearthstone. In this game, there is a game mode "Arena" with the four rules as follows.
1.The record of each player is described as $$$(a,b)$$$, where $$$a$$$ means number of wins, and $$$b$$$ means number of losses. At the beginning of the game, the record is (0,0), that is, 0 wins and 0 losses.
2.For each round, the number of wins in winner's record will be added one point. And the defeated one will be added one point in the number of losses in his record. There is no tie in this game.
3.Each round will be start between two persons with same record. That is, when your record is (a, b), your opponent's record is also (a, b). Obviously, a player with a record of (a+1, b) will be produced after each round, and a record of (a, b+1) players.
4.When someone win N times or lost M times , he will automatically exit and end his game.
In order for everyone to have an opponent before the end of the game, $$$2^{n+m}$$$ players were assigned to participate by Mr. Cocktail.
He will ask q times, and each time he give $$$a, b$$$ and want to know how many people were automatically out of the game with a record of $$$(a,b)$$$. (Guaranteed that $$$(a,b)$$$ meets the exit conditions).
Since the answer may be very large, you only need to output the result after the answer is modulo $$$10^9+7$$$.
In the first line input three integer $$$n,m,q(1 \leq m \lt n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5)$$$ as described in statement.
Then it will input $$$q$$$ lines data. every line will only contain two integer $$$a, b$$$($$$0 \leq a \leq n, 0 \leq b \leq m $$$, ensure that b == m or a == n ).
For each query, output an integer on a line to indicate the answer.
2 1 1 0 1
4
A total of $$$2^{2+1}=8$$$ people with record $$$(0,0)$$$ participating in this game. After the first round, 4 $$$(1,0)$$$ and 4 $$$(0,1)$$$ are generated. Among them, $$$(0,1)$$$ is eliminated directly, and there will be no players with $$$(0,1)$$$ records in subsequent matches, so the answer is 4.
Chino has an array $$$a$$$ with $$$n$$$ elements. Now she prepares $$$m$$$ different arithmetic sequence. The first term of the i-th arithmetic sequence is $$$b_i[0]$$$, the tolerance is $$$k_i$$$, and the length of the sequence is exactly $$$n$$$.
The element of $$$a$$$ marked $$$x$$$ and $$$b$$$ marked $$$y$$$ with same position in respective array. The element in $$$c$$$ in Same position marked $$$z$$$. $$$z$$$ is equal to $$$y$$$ minus $$$x$$$. ( $$$c_i=\{b_i[0]-a[0],b_i[1]-a[1],...,b_i[n-1]-a[n-1]\}$$$)
For each array $$$c$$$, marked $$$Minimum_i$$$ is the minimum element in $$$c_i$$$.
That is $$$Minimum_i=min(c_i[0],c_i[1],...,c_i[n-1])$$$
Now Chino want to know for each different array $$$b_i$$$, what are the generated $$$Minimum_i$$$.
In the first line, input two integer n,m$$$(1 \leq n,m \leq 10^5)$$$ means the length of the array the numbers of arithmetic sequence.
In the next line, input n non-negative integers $$$a[i](0 \leq a[i] \leq 10^{12})$$$
In the next m lines, input two integers $$$b_i[0],k_i(0 \leq b_i[0] \leq 10^{12}, -10^7 \leq k_i \leq 10^7)$$$
Output m lines, Represents each $$$Minimum_i$$$
5 3 1 9 2 4 3 10 -1 1 100 403 -100
0 0 0
$$$b_1=\{10,9,8,7,6\},c_1= \{9,0,6,3,3\}$$$,The minimum value is 0
$$$b_2=\{1,101,201,301,401\},c_2= \{0,92,199,297,398\}$$$,The minimum value is 0
$$$b_3=\{403,303,203,103,3\},c_3= \{401,294,201,99,0\}$$$,The minimum value is 0
Mr. Cocktail get a string contain N characters. The character in the string from left to right respective marked as $$$a_1, a_2 ... a_n$$$. This string consists of lowercase letters only.
Cocktail can perform unlimited times exchange operations on this string. Each operation can choose two digits $$$i,j$$$, satisfying $$$l \leq |i-j| \leq r$$$, and exchange the letters in these two positions—-That is, $$$a_i, a_j$$$.
Cocktail hopes that the lexicographical order of this string after several exchanges is the smallest. Now given this string and $$$l, r$$$, please output a string representing the smallest lexicographical order that Cocktail can achieve after several operations.
In the first line, input three integer, indicating $$$n, l, r(2 \leq n \leq 10^5, 1 \leq l \leq r \lt n)$$$, the meaning is shown in the statement.
The next line input a string $$$a$$$ of length $$$n$$$.Represents the initial string.
Output a string representing the smallest lexicographical string reached after several operations with follow the rules as statement describe.
5 1 1 edcba
abcde
5 4 4 edcba
adcbe
In a remote place, there is a rabbits market where rabbits can be bought and sold in every day. The trading rules in this market are as follows:
1.The market is available only in morning and afternoon in one day. And the rabbit transaction price may be different every day even different between morning and afternoon in a day.
2.It is prohibited that purchasing more than once in a day. And only one rabbit can be purchased at a time.
3. You can only sell once in a day, but you can sell rabbits unlimited quantities (provided that you have so many rabbits)
Mr.Cocktail has traded in this market for N days, suppose he has unlimited money to buy rabbits. Before the first day and after the last day, he has no rabbits. Now, in these N days, how much money did he earn the most?
The first line contains a positive integer N, which means there are N days in total $$$(1 \leq n \leq 10^5)$$$
Next, there are N lines, each line contains two positive integers, representing the rabbit price in the morning and afternoon of the day $$$a_i,b_i(1 \leq a_i ,b_i \leq 10^9)$$$.
Output an integer on a line to indicate the answer.
3 1 6 2 3 7 1
11
2 5 4 3 2
0
In example 1, a rabbit was purchased for $1 in the morning of the first day, and a rabbit was purchased for $2 in the afternoon of the second day. On the morning of the third day, the two rabbits were sold, a total profit of $11.
The price of the rabbit in sample 2 continues to decrease, and it is impossible to make money through buying and selling, so choose not to make any buying and selling, and output the answer 0.
There are N small balls with same weight in horizontal smooth plane. And the volume of these balls can be negligible. All the balls are on the same straight line. There are three possibilities for their initial speed $$$v_0$$$ which is -1 m/s, 0 m/s and 1 m/s.
The initial speed of -1 means that the ball moves to the left along a straight line, the initial speed of 0 means that the ball is still at first, and the initial speed of 1 means that the initial speed of the ball moves to the right in a straight line.
A fully elastic collision occurs when two balls collide against each other.
Fully elastic collision formula is $$$\left\{\begin{matrix}v_1=\frac{(m_1-m_2)v_1+2m_2v_2}{\; \; \; \; \; \; \; \; \; \;m_1+m_2\; \; \; \; \; \; \; \; \; \;}\\ \; \\ v_2=\frac{(m_2-m_1)v_2+2m_1v_1}{\; \; \; \; \; \; \; \; \; \;m_1+m_2\; \; \; \; \; \; \; \; \; \;}\end{matrix}\right.$$$
Among them, $$$m_1, m_2$$$ represent the weight of the two objects that collided. $$$v_1, v_2$$$ represent the speed before the collision.
Don't be worried, this question is not a physics question. You only need to know the exchanging speed at which two objects of exactly the same weight when they collide.
Given the positions and speeds of n balls at the beginning, find their positions k seconds later.
There are two integers in the first input line n,k$$$(1 \leq n \leq 10 ^5, 0 \leq k \leq 10^9 )$$$
In next n input lines, each line of two integers $$$p_i,v_i(-10^9 \leq p_i \leq 10^9,v_i \in \{-1,0,1\})$$$ indicating the initial position and speed of the ball.
It is guaranteed in all input data that all the balls are in different positions at the beginning
There are n integers in a row, and the i-th integer represents the position of the i-th ball after k seconds.
4 10 -10 1 10 -1 -7 0 5 0
-7 5 0 0
2 1 5 1 6 -1
5 6
In the first case, assuming the positive direction is the right side, the ball 1 and ball 3 collide in the 3rd second, and the ball 1 stays in place after the collision. The number 3 ball continues to move to the right. In the 5th second, the No. 2 ball and the No. 4 ball collided. After the collision, the No. 2 ball stayed in place and the No. 4 ball continued to move to the left. In the 10th second, the ball 3 and ball 4 collided. Since the volume of the ball is negligible, it can be considered that the positions of both balls are at 0 at the moment of collision.
In the second case,The two balls collided after 0.5 seconds and then continued to move for 0.5 seconds.
The favorite game of Mr.Cocktail is dota2. Serpentine walking is a useful skill to dodge the enemy's attack. Serpentine walking refers to the path of movement that keeps swing direction like a snake. Suppose the map is a n*m two-dimensional plane. Mr.Cocktail at the point (1,1) in initial.
He will first go to the right to the end, that is, point (n,1). Then turn and go one step upwards to point (n,2). Go to the left again to the end, that is, point (1,2),. Then go one step up, and go to the right again to the end.
The picture above is the action line when n=3 and m=4. Now the map size is n*m . The number of steps k of Cocktail's movement are known. Find the Manhattan distance from the position after k steps to the starting point according to the rule.
Manhattan distance Definition: The distance between two points measured along axes at right angles. In a plane with p1 at (x1, y1) and p2 at (x2, y2), it is |x1 - x2| + |y1 - y2|.
The first line contains a positive integer T, which represents the number of groups to be tested. $$$(1 \leq T \leq 10^4)$$$
Next contains T lines, each row contains three integers $$$n, m, k(1 \leq n, m \leq 10^{18}, 0 \leq k \leq min(n*m-1, 10^{18}))$$$
For each test data, output a line of one coordinate to represent the answer. (A positive integer separated by two spaces represents the x and y coordinates respectively)
5 3 3 1 3 3 2 3 3 3 3 3 4 3 3 5
1 2 3 2 1
There is a cute pony! Oh No, why a wolf chasing it behind?
In a 1*n one-dimensional number axis, the wolf initial position is point $$$x_1$$$, and the pony at point $$$x_2$$$ initially. Each round, the wolf must move $$$v_1$$$ steps, the pony must move $$$v_2$$$ steps. Each step can move one point to the left or right.
Now the pony and the wolf take turns to move. The pony moves first in the first round, then the wolf moves in the second round, and so on.
Means, the pony moves in the 1, 3, 5, 7, 9... rounds, and the wolf moves in the 2, 4, 6, 8... rounds.
If at a certain moment, the wolf and the pony stand in the same position, it means that the wolf has caught the pony. This moment can be in the process of moving.
It is guaranteed that at the beginning, the little pony and the wolf are not in the same point.
The pony wants to delay the rounds he be caught as many as possible, while the wolf hopes to catch the pony earlier. If both the wolf and the little pony are smart enough, in the first few rounds, will the wolf catch the little pony?
Note: During the movement of the wolf or the little horse, they cannot exceed the boundary of the number axis, that is, any position x they move to must satisfy $$$1 \leq x \leq n$$$
The first line of input contains a positive integer T, which represents the number of test cases.$$$(1 \leq T \leq 10^4)$$$
Each test contains five positive integers $$$n, v_1, v_2, x_1, x_2( 2 \leq n \leq 10^3,1 \leq v_1,v_2\leq 10^9, 1 \leq x_1,x_2 \leq n)$$$ and guarantee $$$x_1 \neq x_2 $$$.
The meaning is as shown in the statement.
For each test data, output a positive integer in one line to indicate that the wolf needs several rounds to catch the pony.
1 10 3 1 4 8
4
The pony moves to position 9 in the first round, and the wolf moves to position 7 in the second round. In the third round, the little pony must move, so it can only move to position 8 or 10. No matter which position it is, the wolf can catch up in the fourth round. So output 4.
Chino held a blind date event, there are n male guests and m female guests attending.
The personality characteristic value of each person can be represented by an integer, the personality characteristic value of the i-th male guest is $$$a_i$$$, and the personality characteristic value of the j-th female guest is $$$b_j$$$.
Chino believes that when the calculation result of the personality characteristic values of two people $$$a_i \times b_j$$$ in a certain range [l,r], the personality of two person is suitable each of them.
Chino would like to know how many matching combinations possible satisfied personality suitability between male and female guests.
The first line contain two positive integers $$$n,m(1 \leq n,m \leq 10^5)$$$
The next line contain n integers $$$a_i(-10^9 \leq a_i \leq 10^9)$$$ indicates the personality characteristic value of the male guests.
Then the next line contain m integers$$$b_i(-10^9 \leq b_i \leq 10^9)$$$ indicates the personality characteristic value of the female guests.
the final line only contain two integers $$$l,r(-10^9 \leq l \leq r \leq 10^9)$$$
Output an integer on a line to indicate the number of matching combinations.
5 5 1 2 3 4 5 1 2 3 4 5 1 20
24
3 4 -1 -3 -5 -7 -6 -8 -9 9 9
1
For the first example, except that the male guest 5 and the female guest 5 do not meet the conditions, the other conditions are all legal, so the answer is 25-1=24
For the second example, there is only a legal matching combination for male guest 1 and female guest 4.
NEVER,NEVER,NEVER have $$$a = 2b$$$ in an array!
You have an array $$$P$$$, and each element is denoted as $$$p_1, p_2...p_n$$$. Now you can take any two numbers $$$a$$$ and $$$b$$$ from it. If $$$a = 2 \times b$$$ is satisfied, this array is a "bad array".
Now you need to delete some elements from this array to make it is not "bad array". Please output an integer indicating the minimum number of the elements deleted.
The first line contains a positive integer $$$n(1 \leq n \leq 10^5)$$$ indicates the length of the array.
The next line contains n positive integers separated by spaces $$$p_i(1 \leq p_i \leq 10^6)$$$ Represents each element in the array.
Output an integer on a line to indicate the answer.
5 1 2 4 3 6
2
Deleting 2 and 3 or 2 and 6 can make the situation $$$a = 2 \times b$$$ is not occurring in the array.
In C language, there are two functions for copying arrays, $$$ memcpy $$$ and $$$memmove$$$. These two C language functions have a same purpose is copying the contents of a certain section of memory to a section of memory in units of bytes.
The difference between these two functions is that $$$ memcpy $$$ does not check whether the source address range and the destination address range in memory have overlapping parts. It follows the logic of copying each byte sequentially from left to right, so that can cause the data copied is not equal to original data.
When using the $$$memmove$$$ function, if the source address range and the destination address range have overlapping part, $$$memmove$$$ will do special processing to ensure that the memory of the destination address range is filled with original data.
Now suppose that both the $$$memcpy$$$ and $$$memmove$$$ function calls require three parameters, $$$p_1, p_2, l$$$, which respectively represent the source address, destination address, and the number of bytes copied. For example, given a string "abcdefg", if you call $$$memcopy(1,3,5)$$$, the result will be "abababa", if you call $$$memmove(1,3,5)$$$, the result will be It is "ababcde".
Now give you a string S, and three call parameters, $$$p_1, p_2, l$$$. Please tell Chino what the calling results of $$$memcopy$$$ and $$$memmove$$$ respectively are.
The first line of input data contains only a positive integer $$$n(1 \leq n \leq 10^5)$$$ indicates the length of the string.
The second line of input data contain a string S of length n. S includes only lowercase English letters.
The third line of input data contain three integers $$$p_1,p_2,l(1 \leq p_1,p_2,l \leq n)$$$
And guarantee $$$1 \leq p_1+l-1,p_2+l-1 \leq n$$$ represents the parameters of calling two functions .
Please output two lines, the first line represents the result of calling the $$$memcopy$$$ function, the second line represents the result of calling $$$memmove$$$.
7 abcdefg 1 3 5
abababa ababcde