The head of information security department of a large corporation thinks it's about time he changed the passwords on all computers used by the corporation. The characters which are used in the old passwords and can be used in the new passwords are:
- lowercase Latin letters;
- uppercase Latin letters;
- digits.
You have to write the program that, given the old password $$$s$$$ and the required length of the new password $$$k$$$, generates a new password according to the following constraints:
- the new password should consist of exactly $$$k$$$ characters;
- all characters of the new password should be different (same Latin letters in different cases are considered different, for example, 'a' and 'A' are different characters);
- if a character appears in the old password, it should not appear in the new one.
If it is impossible to generate a new password according to these constraints, your program should report it.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.
Each test case consists of three lines:
- the first line contains one integer $$$k$$$ ($$$1 \le k \le 62$$$) — the desired length of the new password;
- the second line contains one integer $$$n$$$ ($$$1 \le n \le 62$$$) — the length of the old password;
- the third line contains one string $$$s$$$ ($$$|s| = n$$$) — the old password, consisting of lowercase Latin letters, uppercase Latin letters, and/or digits. Note that there can be repeated characters in the old password.
For each test case, print the answer on a separate line as follows:
- if it is impossible to generate a new password, print a single hyphen (character '-' with ASCII code 45);
- otherwise, print the new password. If there are multiple possible passwords, you can print any of them.
51024makethenewpasswordstrong603abc136xyzuvw31320aa1b2c3d4efghijklmABCDEFGHIJKLM31320a1b2c3d4e5fghijklmABCDEFGHIJKLM
1234567890 - donthackmepls 6789NzOyPxQwRvSuTtUsVrWqXpYoZn5 -
You are given a string consisting of characters 0 and/or 1. You have to paint every character of this string into one of two colors, red or blue.
If you paint the $$$i$$$-th character red, you get $$$r_i$$$ coins. If you paint it blue, you get $$$b_i$$$ coins.
After coloring the string, you remove every blue character from it, and count the number of inversions in the resulting string (i. e. the number of pairs of characters such that the left character in the pair is 1, and the right character in the pair is 0). For each inversion, you have to pay $$$1$$$ coin.
What is the maximum number of coins you can earn?
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each test case consists of four lines:
- the first line contains one integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the length of the string;
- the second line contains $$$s$$$ — a string of $$$n$$$ characters, where each character is either 0 or 1;
- the third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^{12}$$$);
- the fourth line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$).
Additional constraint on the input: the sum of values of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.
For each test case, print one integer — the maximum number of coins you can earn.
4701000106 6 6 7 7 6 63 3 5 4 7 6 75101119 8 5 7 54 4 7 8 41001000000007 7 6 5 2 2 5 3 8 38 6 9 6 6 8 9 7 7 98010100008 7 7 7 8 7 7 84 4 4 2 1 4 4 4
43 36 76 52
Monocarp has a robot that can move on a coordinate plane. Initially, the robot is located at point $$$(0, 0)$$$. The robot can move strictly to the right, strictly down, strictly to the left, or strictly up by a distance of one unit. Moving to the left and right corresponds to changing the $$$x$$$ coordinate by $$$-1$$$ and $$$+1$$$, respectively. Moving down and up corresponds to changing the $$$y$$$ coordinate by $$$-1$$$ and $$$+1$$$, respectively.
One of the robot's wheels is malfunctioning, so it is limited in its movements and can move as follows:
- the first movement of the robot must be either to the right or down;
- after moving to the right, the robot can move either to the right or down;
- after moving down, the robot can move either down or to the left;
- after moving to the left, the robot can move either to the left or up;
- after moving up, it can move either up or to the right.
The robot is given a sequence of points. It must visit the first point in the sequence, then the second point, and so on.
Your task is to determine the minimum time it takes for the robot to visit all the points, starting at the cell $$$(0, 0)$$$.
Note that if the robot has already visited a point that appears later in the given sequence, it must still visit it when necessary. Refer to the explanations for the examples for a better understanding of the statement.
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of points that the robot has to visit.
In the $$$i$$$-th of the following lines, there are two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^{9} \le x_i, y_i \le 10^{9}$$$) — the coordinates of the point that the robot must visit in the $$$i$$$-th order.
Note that the points can be repeated. The robot will have to visit the point again each time it appears in the given sequence of points.
Output one integer — the minimum number of moves it takes for the broken robot to visit all the specified points in the required order.
4 2 0 1 1 1 5 1 5
10
3 0 0 -4 -2 0 0
12
2 1000000000 1000000000 -1000000000 -1000000000
6000000004
In the first example, the robot can move to the right twice to reach the first point $$$(2, 0)$$$. Then, the robot can move down once, then left once, and then up twice to reach the second point $$$(1, 1)$$$. After that, the robot can move up four times to reach the third point $$$(1, 5)$$$. Then, the robot doesn't need to move because the fourth point coincides with the third point, and it is already there. Thus, the robot will visit all the points in $$$2 + 4 + 4 = 10$$$ moves.
In the second example, the robot is already at the point $$$(0, 0)$$$, so the first point is considered visited. Then, the robot can move down twice, and then move left four times to reach the second point $$$(-4, -2)$$$. After that, the robot can move up twice and move right four times to reach the third point $$$(0, 0)$$$. Thus, the robot will visit all the points in $$$6 + 6 = 12$$$ moves.
Monocarp and Bicarp are playing a card game. Each card has two parameters: an attack value and a defence value. A card $$$s$$$ beats another card $$$t$$$ if the attack of $$$s$$$ is strictly greater than the defence of $$$t$$$.
Monocarp has $$$n$$$ cards, the $$$i$$$-th of them has an attack value of $$$\mathit{ax}_i$$$ and a defence value of $$$\mathit{ay}_i$$$. Bicarp has $$$m$$$ cards, the $$$j$$$-th of them has an attack value of $$$\mathit{bx}_j$$$ and a defence value of $$$\mathit{by}_j$$$.
On the first move, Monocarp chooses one of his cards and plays it. Bicarp has to respond with his own card that beats that card. After that, Monocarp has to respond with a card that beats Bicarp's card. After that, it's Bicarp's turn, and so forth.
After a card is beaten, it returns to the hand of the player who played it. The game ends when the current player has no cards that beat the card which their opponent just played.
If the game lasts for $$$100^{500}$$$ moves, it's declared a draw.
Both Monocarp and Bicarp play optimally. That is, if they have a winning strategy regardless of their opponent's moves, they play for a win. Otherwise, if they have a drawing strategy, they play for a draw.
You are asked to calculate three values:
- the number of Monocarp's starting moves that result in a win for Monocarp;
- the number of Monocarp's starting moves that result in a draw;
- the number of Monocarp's starting moves that result in a win for Bicarp.
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 an integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of cards Monocarp has.
The second line contains $$$n$$$ integers $$$\mathit{ax}_1, \mathit{ax}_2, \dots, \mathit{ax}_n$$$ ($$$1 \le \mathit{ax}_i \le 10^6$$$) — the attack values of Monocarp's cards.
The third line contains $$$n$$$ integers $$$\mathit{ay}_1, \mathit{ay}_2, \dots, \mathit{ay}_n$$$ ($$$1 \le \mathit{ay}_i \le 10^6$$$) — the defence values of Monocarp's cards.
The fourth line contains a single integer $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — the number of cards Bicarp has.
The fifth line contains $$$m$$$ integers $$$\mathit{bx}_1, \mathit{bx}_2, \dots, \mathit{bx}_m$$$ ($$$1 \le \mathit{bx}_j \le 10^6$$$) — the attack values of Bicarp's cards.
The sixth line contains $$$m$$$ integers $$$\mathit{by}_1, \mathit{by}_2, \dots, \mathit{by}_m$$$ ($$$1 \le \mathit{by}_j \le 10^6$$$) — the defence values of Bicarp's cards.
Additional constraints on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$, the sum of $$$m$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.
For each test case, print three integers:
- the number of Monocarp's starting moves that result in a win for Monocarp;
- the number of Monocarp's starting moves that result in a draw;
- the number of Monocarp's starting moves that result in a win for Bicarp.
338 7 47 1 1028 45 1098 8 5 5 5 4 4 1 42 7 5 2 8 9 7 1 9109 8 7 6 5 5 4 3 2 17 1 6 7 5 8 8 4 9 611051105
1 1 1 2 4 3 0 1 0
The recently-designed electronic board has $$$n$$$ pins numbered from $$$1$$$ to $$$n$$$, arranged in a single row. Several jumpers are going to be put on top of the pins. There are $$$m$$$ jumpers in total, numbered from $$$1$$$ to $$$m$$$. Each jumper is characterised by two numbers — $$$l_j$$$ and $$$r_j$$$: being installed, the $$$j$$$-th jumper covers a contiguous range of pins from $$$l_j$$$ to $$$r_j$$$ (inclusive). Each jumper is constructed in a such way that it will not fit any other position.
Jumper installation process is fully automated. Installation is performed by a very intelligent and innovative robot called InnoKentij as follows.
There is a conveyor, which supplies jumpers to InnoKentij one by one from jumper number $$$1$$$ to jumper number $$$m$$$. For each jumper $$$j$$$, InnoKentij needs to decide whether to install it. If all the pins from $$$l_j$$$ to $$$r_j$$$ (inclusive) are free, InnoKentij simply installs the $$$j$$$-th jumper, and the process continues. But it can happen that the $$$j$$$-th jumper is conflicting with some of previously installed jumpers. Two jumpers are called conflicting if their installation ranges share at least one pin. In case of a conflict, InnoKentij has the following two options:
- discard the $$$j$$$-th jumper;
- discard all previously installed jumpers which conflict with the $$$j$$$-th jumper, and install the jumper number $$$j$$$.
Given the configuration of jumpers, you should emulate the work of robot InnoKentij.
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 4\cdot10^5$$$; $$$1 \le m \le 2\cdot10^5$$$) — the number of pins on the electronic board and the number of jumpers.
The next $$$m$$$ lines describe the jumpers: the $$$j$$$-th of them contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the installation position of the $$$j$$$-th jumper.
You should output the work log of the robot InnoKentij. The log should contain exactly $$$m$$$ lines, the $$$j$$$-th line corresponding to the actions pefrormed by InnoKentij when it was supplied with the $$$j$$$-th jumper from the conveyor. The first integer in $$$j$$$-th line should be $$$1$$$ if the $$$j$$$-th jumper was installed, or $$$0$$$ if it was discarded. The second integer in the $$$j$$$-th line (let's denote it by $$$d_j$$$) should be equal to the number of conflicting jumpers which were discarded (this number can be $$$0$$$ if there were no conflicting jumpers, or if the $$$j$$$-th jumper was discarded). Then, $$$d_j$$$ integers should follow — the indices of the jumpers InnoKentij removed in ascending order.
10 52 34 54 63 63 10
1 0 1 0 1 1 2 0 0 1 2 1 3
7 45 62 21 11 6
1 0 1 0 1 0 1 3 1 2 3
9 65 54 63 72 83 71 9
1 0 1 1 1 1 1 2 1 1 3 0 0 1 1 4
Some time ago, the owner of the cat Benedict decided that her pet was lonely while she was at work. So, she got a kitten named Tybalt.
Every morning, Benedict's owner takes two packs of food and puts the contents of the packs into two bowls (one bowl for each pack). Benedict's owner likes order, so the food packs are arranged in some order, and she plans to give them to the cats in that order. In other words, packs $$$1$$$ and $$$2$$$ are planned to be used on day $$$1$$$, packs $$$3$$$ and $$$4$$$ are planned to be used on day $$$2$$$, and so on.
There are $$$n$$$ types of food in total; for simplicity, let's assume that the food types are numbered from $$$1$$$ to $$$n$$$.
Each cat has its own personal rating of the food. The cat's rating is a list of food types, starting with the one the cat likes the most and ending with the one the cat likes the least. In other words, the earlier a food type appears in the list, the more the cat likes that food type.
So, when the owner fills both bowls, each cat runs to the bowl that contains the food with a higher rating from that cat's perspective. Sometimes both cats run to the same bowl. However, when they finish eating the contents of that bowl, they move on to eat from the other bowl.
If the bowls have the same food, the cats, upon realizing this, will eat from different bowls.
The owner wants to minimize the number of days that both cats eat from the same bowl. However, she doesn't want to change the order of using the food packs too much. If she plans to give a certain food pack on day $$$k$$$, she can use that pack on day $$$k$$$, day $$$k-1$$$ or day $$$k+1$$$, but not earlier or later. On each day, exactly two food packs should be used.
Your task is to determine the minimum possible number of days that both cats eat from the same bowl based on the food ratings for each cat and the owner's planned order of giving out the food.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$2 \le m \le 2 \cdot 10^5$$$; $$$m$$$ is even) — the number of types of food and the number of food packs, respectively.
The second line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$) — the cat Benedict's food rating. All $$$b_i$$$ are distinct.
The third line contains $$$n$$$ integers $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_j \le n$$$) — the kitten Tybalt's food rating. All $$$t_j$$$ are distinct.
The fourth line contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \le a_p \le n$$$) — the initial order of food packs.
Output a single integer — the minimum possible number of days that both cats eat from the same bowl.
5 14 4 3 1 2 5 5 3 1 4 2 4 3 4 4 2 1 5 3 5 5 3 2 1 4
0
5 12 3 5 4 1 2 2 3 4 5 1 3 5 4 1 5 1 3 4 3 1 5 3
2
4 12 3 4 1 2 2 3 4 1 3 1 4 3 3 1 2 2 3 2 4 1
0
5 14 3 5 4 1 2 2 3 4 5 1 3 5 4 1 5 1 3 4 3 1 5 3 2 4
1
A ticket is a non-empty string of digits from $$$1$$$ to $$$9$$$.
A lucky ticket is such a ticket that:
- it has an even length;
- the sum of digits in the first half is equal to the sum of digits in the second half.
You are given $$$n$$$ ticket pieces $$$s_1, s_2, \dots, s_n$$$. How many pairs $$$(i, j)$$$ (for $$$1 \le i, j \le n$$$) are there such that $$$s_i + s_j$$$ is a lucky ticket? Note that it's possible that $$$i=j$$$.
Here, the + operator denotes the concatenation of the two strings. For example, if $$$s_i$$$ is 13, and $$$s_j$$$ is 37, then $$$s_i + s_j$$$ is 1337.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of ticket pieces.
The second line contains $$$n$$$ non-empty strings $$$s_1, s_2, \dots, s_n$$$, each of length at most $$$5$$$ and consisting only of digits from $$$1$$$ to $$$9$$$.
Print a single integer — the number of pairs $$$(i, j)$$$ (for $$$1 \le i, j \le n$$$) such that $$$s_i + s_j$$$ is a lucky ticket.
105 93746 59 3746 593 746 5937 46 59374 6
20
52 22 222 2222 22222
13
312 34 56
3
Let's call an array $$$a$$$ of $$$n$$$ non-negative integers fancy if the following conditions hold:
- at least one from the numbers $$$x$$$, $$$x + 1$$$, ..., $$$x+k-1$$$ appears in the array;
- consecutive elements of the array differ by at most $$$k$$$ (i.e. $$$|a_i-a_{i-1}| \le k$$$ for each $$$i \in [2, n]$$$).
You are given $$$n$$$, $$$x$$$ and $$$k$$$. Your task is to calculate the number of fancy arrays of length $$$n$$$. Since the answer can be large, print it modulo $$$10^9+7$$$.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases.
The only line of each test case contains three integers $$$n$$$, $$$x$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$; $$$0 \le x \le 40$$$).
For each test case, print a single integer — the number of fancy arrays of length $$$n$$$, taken modulo $$$10^9+7$$$.
43 0 11 4 254 7 21000000000 40 1000000000
9 25 582 514035484
In the first test case of the example, the following arrays are fancy:
- $$$[0, 0, 0]$$$;
- $$$[0, 0, 1]$$$;
- $$$[0, 1, 0]$$$;
- $$$[0, 1, 1]$$$;
- $$$[0, 1, 2]$$$;
- $$$[1, 0, 0]$$$;
- $$$[1, 0, 1]$$$;
- $$$[1, 1, 0]$$$;
- $$$[2, 1, 0]$$$.
You are given a sequence of integers $$$a$$$ of length $$$2n$$$. You have to split these $$$2n$$$ integers into $$$n$$$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $$$a$$$ should become the $$$x$$$ or $$$y$$$ coordinate of exactly one point. Note that some points can be equal.
After the points are formed, you have to choose a path $$$s$$$ that starts from one of these points, ends at one of these points, and visits all $$$n$$$ points at least once.
The length of path $$$s$$$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as $$$|x_1-x_2| + |y_1-y_2|$$$.
Your task is to form $$$n$$$ points and choose a path $$$s$$$ in such a way that the length of path $$$s$$$ is minimized.
The first line contains an integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of points to be formed.
The next line contains $$$2n$$$ integers $$$a_1, a_2, \dots, a_{2n}$$$ ($$$0 \le a_i \le 1\,000$$$) — the description of the sequence $$$a$$$.
Print the minimum possible length of path $$$s$$$ in the first line.
In the $$$i$$$-th of the following $$$n$$$ lines, print two integers $$$x_i$$$ and $$$y_i$$$ — the coordinates of the point that needs to be visited at the $$$i$$$-th position.
If there are multiple answers, print any of them.
2 15 1 10 5
9 10 1 15 5
3 10 30 20 20 30 10
20 20 20 10 30 10 30
In the first example, for instance, you can form points $$$(10, 1)$$$ and $$$(15, 5)$$$ and start the path $$$s$$$ from the first point and end it at the second point. Then the length of the path will be $$$|10 - 15| + |1 - 5| = 5 + 4 = 9$$$.
In the second example, you can form points $$$(20, 20)$$$, $$$(10, 30)$$$, and $$$(10, 30)$$$, and visit them in that exact order. Then the length of the path will be $$$|20 - 10| + |20 - 30| + |10 - 10| + |30 - 30| = 10 + 10 + 0 + 0 = 20$$$.
You are given an incomplete permutation of length $$$2n - 1$$$, where only odd positions are filled in with odd numbers from $$$1$$$ to $$$2n-1$$$. Complete the permutation by filling in even positions with even numbers from $$$2$$$ to $$$2n-2$$$ so that no even number is a local extremum.
A permutation of length $$$k$$$ is an array of length $$$k$$$ which contains every integer from $$$1$$$ to $$$k$$$ (inclusive) exactly once. For example, $$$p=[4, 2, 6, 5, 3, 1]$$$ is a permutation of length $$$6$$$.
An element of a permutation is a local extremum if it is either greater than both its neighbours, or less than both its neighbours.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of odd integers in the permutation.
The second line contains $$$n$$$ integers $$$p_1, p_3, p_5, \dots, p_{2n-1}$$$ ($$$1 \le a_i \le 2n-1$$$, all $$$p_i$$$ are odd and unique) — the elements on the odd positions of the permutation.
Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.
For each test case, print the answer on a separate line as follows:
- if the answer exists, print $$$n - 1$$$ integers $$$p_2, p_4, p_6, \dots, p_{2n-2}$$$ ($$$2 \le p_i \le 2n-2$$$). All these integers should be even and unique. In the permutation $$$[p_1, p_2, \dots, p_{2n-1}]$$$, no integer on an even position should be a local extremum. In case there are multiple answers, you may print any of them;
- otherwise, print one integer $$$-1$$$.
331 3 5813 15 9 5 7 1 3 1151 5 3 9 7
2 4 14 12 8 6 4 2 10 2 4 6 8
In the first test case of the example, you are given an incomplete permutation $$$[1, \_, 3, \_, 5]$$$, where underscores denote missing even numbers. The sample output provides the only valid solution for that test case: $$$[1, 2, 3, 4, 5]$$$.
The only other way to insert even numbers into the given incomplete permutation is $$$[1, 4, 3, 2, 5]$$$, and that violates the extremum requirement, as here $$$4$$$ is greater than both its neighbours $$$1$$$ and $$$3$$$.
Gennady is a big spender, and as a result he is constantly broke. Being tired of that, Gennady devised a strategy to get his finances in order.
Right now he has $$$0$$$ coins. For each of the next $$$n$$$ days, he knows how much money he will earn (during the $$$i$$$-th day, he will earn $$$a_i$$$ coins). During each day, after receiving the coins, Gennady plans to go shopping and spend $$$X$$$ coins ($$$X$$$ is the same for all days). If he has less than $$$X$$$ coins when he goes shopping, he will simply spend them all, i.e. he will have $$$0$$$ coins at the beginning of the next day. Otherwise, he will spend exactly $$$X$$$ coins.
You have to process $$$q$$$ queries. The $$$j$$$-th query consists of a single number $$$X_j$$$, and your task is to find out how much money Gennady will have after $$$n$$$ days if he uses that value as $$$X$$$ in his strategy.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le q \le 10^5$$$) — the number of days to consider and the number of queries.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of coins Gennady earns during the $$$i$$$-th day.
The third line contains $$$q$$$ integers $$$X_1, X_2, \dots, X_q$$$, where $$$X_j$$$ ($$$0 \le X_j \le 10^9$$$) — the value of $$$X$$$ for the $$$j$$$-th query.
Print $$$q$$$ integers. The $$$j$$$-th integer should be the answer to the $$$j$$$-th query.
3 5 1 2 3 0 1 2 3 4
6 3 1 0 0
6 5 0 11 100 0 20 57 27 10 40 5 67
69 138 17 163 0
The third query from the example is processed as follows:
- on the first day, Gennady earns $$$1$$$ coin;
- Gennady plans to spend $$$2$$$ coins. But since he has only $$$1$$$ coin, he spends it and has $$$0$$$ coins left;
- on the second day, Gennady earns $$$2$$$ coins;
- he spends these $$$2$$$ coins the same day, and at the end of the day, he has $$$0$$$ coins left;
- on the third day, Gennady earns $$$3$$$ coins;
- he spends $$$2$$$ coins that day, and at the end of the day, he has $$$1$$$ coin left.
Monocarp likes computer games. He uses the game distribution system "Mist" to download and install games.
There are $$$n$$$ games available in Monocarp's Mist account. The $$$i$$$-th game has two parameters:
- $$$s_i$$$ — the size of the game (the number of megabytes it occupies if installed);
- $$$r_i$$$ — the rating of the game for Monocarp.
Monocarp's computer has $$$m$$$ megabytes of free space. Monocarp won't install just one game; he wants to install at least $$$k$$$ games on his computer.
After installing the games, he will choose the $$$x$$$-th highest rated installed game and start playing it (i.e. if $$$x = 1$$$, he will choose the highest rated of the installed games, if $$$x = 2$$$, the second highest rated, and so on).
Your task is to calculate the maximum possible rating of a game that Monocarp can play, if he has to install at least $$$k$$$ games with total size not exceeding $$$m$$$. If it is impossible to install at least $$$k$$$ games, you should report it.
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 four integers $$$n$$$, $$$k$$$, $$$x$$$ and $$$m$$$ ($$$1 \le x \le k \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^{14}$$$).
The second line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$).
The third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^9$$$).
Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.
For each test case, print a single integer — the maximum possible rating of a game that Monocarp can play, if he has to install at least $$$k$$$ games with total size not exceeding $$$m$$$. If it is impossible to install at least $$$k$$$ games, you should print $$$-1$$$.
43 2 2 51 2 41 4 21 1 1 1326 3 2 63 2 4 1 2 14 3 2 1 3 12 2 1 32 11 1
1 -1 3 1
In the first example, Monocarp can install games $$$[1, 2]$$$ — the answer will be $$$1$$$, since it's the rating of the $$$2$$$-nd highest rated installed game. Games $$$[1, 3]$$$ will lead to the same answer. Games $$$[2, 3]$$$ can't be installed because their total size is $$$6$$$.
In the second example, the game size is greater than $$$m$$$, so the answer is $$$-1$$$.
In the third example, one of the possible set of games that lead to the answer $$$3$$$ is $$$[2, 4, 5, 6]$$$.
Monocarp has found a treasure map. The map represents the treasure location as an OX axis. Monocarp is at $$$0$$$, the treasure chest is at $$$x$$$, the key to the chest is at $$$y$$$.
Obviously, Monocarp wants to open the chest. He can perform the following actions:
- go $$$1$$$ to the left or $$$1$$$ to the right (spending $$$1$$$ second);
- pick the key or the chest up if he is in the same point as that object (spending $$$0$$$ seconds);
- put the chest down in his current point (spending $$$0$$$ seconds);
- open the chest if he's in the same point as the chest and has picked the key up (spending $$$0$$$ seconds).
Monocarp can carry the chest, but the chest is pretty heavy. He knows that he can carry it for at most $$$k$$$ seconds in total (putting it down and picking it back up doesn't reset his stamina).
What's the smallest time required for Monocarp to open the chest?
The only line contains three integers $$$x, y$$$ and $$$k$$$ ($$$1 \le x, y \le 100$$$; $$$x \neq y$$$; $$$0 \le k \le 100$$$) — the initial point of the chest, the point where the key is located, and the maximum time Monocarp can carry the chest for.
Print a single integer — the smallest time required for Monocarp to open the chest.
5 7 2
7
10 5 0
10
You are given $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$.
Your task is to construct an array $$$b_1, b_2, \dots, b_n$$$ such that:
- every integer from $$$0$$$ to $$$n-1$$$ appears in $$$b$$$ exactly once;
- for every $$$i$$$ from $$$1$$$ to $$$n-1$$$, $$$b_i \oplus b_{i+1} = a_i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operator).
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).
The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 2n$$$).
Additional constraint on the input: it's always possible to construct at least one valid array $$$b$$$ from the given sequence $$$a$$$.
Print $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$. If there are multiple such arrays, you may print any of them.
42 1 2
0 2 3 1
61 6 1 4 1
2 3 5 4 0 1