Gennady owns a small hotel in the countryside where he lives a peaceful life. He loves to take long walks, watch sunsets and play cards with tourists staying in his hotel. His favorite game is called "Mau-Mau".
To play Mau-Mau, you need a pack of $$$52$$$ cards. Each card has a suit (Diamonds — D, Clubs — C, Spades — S, or Hearts — H), and a rank (2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, or A).
At the start of the game, there is one card on the table and you have five cards in your hand. You can play a card from your hand if and only if it has the same rank or the same suit as the card on the table.
In order to check if you'd be a good playing partner, Gennady has prepared a task for you. Given the card on the table and five cards in your hand, check if you can play at least one card.
The first line of the input contains one string which describes the card on the table. The second line contains five strings which describe the cards in your hand.
Each string is two characters long. The first character denotes the rank and belongs to the set $$$\{{\tt 2}, {\tt 3}, {\tt 4}, {\tt 5}, {\tt 6}, {\tt 7}, {\tt 8}, {\tt 9}, {\tt T}, {\tt J}, {\tt Q}, {\tt K}, {\tt A}\}$$$. The second character denotes the suit and belongs to the set $$$\{{\tt D}, {\tt C}, {\tt S}, {\tt H}\}$$$.
All the cards in the input are different.
If it is possible to play a card from your hand, print one word "YES". Otherwise, print "NO".
You can print each letter in any case (upper or lower).
AS 2H 4C TH JH AD
YES
2H 3D 4C AC KD AS
NO
4D AS AC AD AH 5H
YES
In the first example, there is an Ace of Spades (AS) on the table. You can play an Ace of Diamonds (AD) because both of them are Aces.
In the second example, you cannot play any card.
In the third example, you can play an Ace of Diamonds (AD) because it has the same suit as a Four of Diamonds (4D), which lies on the table.
You are given $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. With a cost of one coin you can perform the following operation:
Choose one of these numbers and add or subtract $$$1$$$ from it.
In particular, we can apply this operation to the same number several times.
We want to make the product of all these numbers equal to $$$1$$$, in other words, we want $$$a_1 \cdot a_2$$$ $$$\dots$$$ $$$\cdot a_n = 1$$$.
For example, for $$$n = 3$$$ and numbers $$$[1, -3, 0]$$$ we can make product equal to $$$1$$$ in $$$3$$$ coins: add $$$1$$$ to second element, add $$$1$$$ to second element again, subtract $$$1$$$ from third element, so that array becomes $$$[1, -1, -1]$$$. And $$$1\cdot (-1) \cdot (-1) = 1$$$.
What is the minimum cost we will have to pay to do that?
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of numbers.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the numbers.
Output a single number — the minimal number of coins you need to pay to make the product equal to $$$1$$$.
2 -1 1
2
4 0 0 0 0
4
5 -5 -3 5 3 0
13
In the first example, you can change $$$1$$$ to $$$-1$$$ or $$$-1$$$ to $$$1$$$ in $$$2$$$ coins.
In the second example, you have to apply at least $$$4$$$ operations for the product not to be $$$0$$$.
In the third example, you can change $$$-5$$$ to $$$-1$$$ in $$$4$$$ coins, $$$-3$$$ to $$$-1$$$ in $$$2$$$ coins, $$$5$$$ to $$$1$$$ in $$$4$$$ coins, $$$3$$$ to $$$1$$$ in $$$2$$$ coins, $$$0$$$ to $$$1$$$ in $$$1$$$ coin.
Alice and Bob have received three big piles of candies as a gift. Now they want to divide these candies as fair as possible. To do this, Alice takes one pile of candies, then Bob takes one of the other two piles. The last pile is split between Alice and Bob as they want: for example, it is possible that Alice takes the whole pile, and Bob gets nothing from it.
After taking the candies from the piles, if Alice has more candies than Bob, she discards some candies so that the number of candies she has is equal to the number of candies Bob has. Of course, Bob does the same if he has more candies.
Alice and Bob want to have as many candies as possible, and they plan the process of dividing candies accordingly. Please calculate the maximum number of candies Alice can have after this division process (of course, Bob will have the same number of candies).
You have to answer $$$q$$$ independent queries.
Let's see the following example: $$$[1, 3, 4]$$$. Then Alice can choose the third pile, Bob can take the second pile, and then the only candy from the first pile goes to Bob — then Alice has $$$4$$$ candies, and Bob has $$$4$$$ candies.
Another example is $$$[1, 10, 100]$$$. Then Alice can choose the second pile, Bob can choose the first pile, and candies from the third pile can be divided in such a way that Bob takes $$$54$$$ candies, and Alice takes $$$46$$$ candies. Now Bob has $$$55$$$ candies, and Alice has $$$56$$$ candies, so she has to discard one candy — and after that, she has $$$55$$$ candies too.
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 1000$$$) — the number of queries. Then $$$q$$$ queries follow.
The only line of the query contains three integers $$$a, b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^{16}$$$) — the number of candies in the first, second and third piles correspondingly.
Print $$$q$$$ lines. The $$$i$$$-th line should contain the answer for the $$$i$$$-th query — the maximum number of candies Alice can have after the division, if both Alice and Bob act optimally (of course, Bob will have the same number of candies).
4 1 3 4 1 10 100 10000000000000000 10000000000000000 10000000000000000 23 34 45
4 55 15000000000000000 51
Maria is the most active old lady in her house. She was tired of sitting at home. She decided to organize a ceremony against the coronavirus.
She has $$$n$$$ friends who are also grannies (Maria is not included in this number). The $$$i$$$-th granny is ready to attend the ceremony, provided that at the time of her appearance in the courtyard there will be at least $$$a_i$$$ other grannies there. Note that grannies can come into the courtyard at the same time. Formally, the granny $$$i$$$ agrees to come if the number of other grannies who came earlier or at the same time with her is greater than or equal to $$$a_i$$$.
Grannies gather in the courtyard like that.
- Initially, only Maria is in the courtyard (that is, the initial number of grannies in the courtyard is $$$1$$$). All the remaining $$$n$$$ grannies are still sitting at home.
- On each step Maria selects a subset of grannies, none of whom have yet to enter the courtyard. She promises each of them that at the time of her appearance there will be at least $$$a_i$$$ other grannies (including Maria) in the courtyard. Maria can call several grannies at once. In this case, the selected grannies will go out into the courtyard at the same moment of time.
- She cannot deceive grannies, that is, the situation when the $$$i$$$-th granny in the moment of appearing in the courtyard, finds that now there are strictly less than $$$a_i$$$ other grannies (except herself, but including Maria), is prohibited. Please note that if several grannies appeared in the yard at the same time, then each of them sees others at the time of appearance.
Your task is to find what maximum number of grannies (including herself) Maria can collect in the courtyard for the ceremony. After all, the more people in one place during quarantine, the more effective the ceremony!
Consider an example: if $$$n=6$$$ and $$$a=[1,5,4,5,1,9]$$$, then:
- at the first step Maria can call grannies with numbers $$$1$$$ and $$$5$$$, each of them will see two grannies at the moment of going out into the yard (note that $$$a_1=1 \le 2$$$ and $$$a_5=1 \le 2$$$);
- at the second step, Maria can call grannies with numbers $$$2$$$, $$$3$$$ and $$$4$$$, each of them will see five grannies at the moment of going out into the yard (note that $$$a_2=5 \le 5$$$, $$$a_3=4 \le 5$$$ and $$$a_4=5 \le 5$$$);
- the $$$6$$$-th granny cannot be called into the yard — therefore, the answer is $$$6$$$ (Maria herself and another $$$5$$$ grannies).
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then test cases follow.
The first line of a test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of grannies (Maria is not included in this number).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$).
It is guaranteed that the sum of the values $$$n$$$ over all test cases of the input does not exceed $$$10^5$$$.
For each test case, print a single integer $$$k$$$ ($$$1 \le k \le n + 1$$$) — the maximum possible number of grannies in the courtyard.
4 5 1 1 2 2 1 6 2 3 4 5 6 7 6 1 5 4 5 1 9 5 1 2 3 5 6
6 1 6 4
In the first test case in the example, on the first step Maria can call all the grannies. Then each of them will see five grannies when they come out. Therefore, Maria and five other grannies will be in the yard.
In the second test case in the example, no one can be in the yard, so Maria will remain there alone.
The third test case in the example is described in the details above.
In the fourth test case in the example, on the first step Maria can call grannies with numbers $$$1$$$, $$$2$$$ and $$$3$$$. If on the second step Maria calls $$$4$$$ or $$$5$$$ (one of them), then when a granny appears in the yard, she will see only four grannies (but it is forbidden). It means that Maria can't call the $$$4$$$-th granny or the $$$5$$$-th granny separately (one of them). If she calls both: $$$4$$$ and $$$5$$$, then when they appear, they will see $$$4+1=5$$$ grannies. Despite the fact that it is enough for the $$$4$$$-th granny, the $$$5$$$-th granny is not satisfied. So, Maria cannot call both the $$$4$$$-th granny and the $$$5$$$-th granny at the same time. That is, Maria and three grannies from the first step will be in the yard in total.
A magic number is a number formed by concatenation of numbers 1, 14 and 144. We can use each of these numbers any number of times. Therefore 14144, 141414 and 1411 are magic numbers but 1444, 514 and 414 are not.
You're given a number. Determine if it is a magic number or not.
The first line of input contains an integer n, (1 ≤ n ≤ 109). This number doesn't contain leading zeros.
Print "YES" if n is a magic number or print "NO" if it's not.
114114
YES
1111
YES
441231
NO
You are given a rectangular cake, represented as an r × c grid. Each cell either has an evil strawberry, or is empty. For example, a 3 × 4 cake may look as follows:
The cakeminator is going to eat the cake! Each time he eats, he chooses a row or a column that does not contain any evil strawberries and contains at least one cake cell that has not been eaten before, and eats all the cake cells there. He may decide to eat any number of times.
Please output the maximum number of cake cells that the cakeminator can eat.
The first line contains two integers r and c (2 ≤ r, c ≤ 10), denoting the number of rows and the number of columns of the cake. The next r lines each contains c characters — the j-th character of the i-th line denotes the content of the cell at row i and column j, and is either one of these:
- '.' character denotes a cake cell with no evil strawberry;
- 'S' character denotes a cake cell with an evil strawberry.
Output the maximum number of cake cells that the cakeminator can eat.
3 4
S...
....
..S.
8
For the first example, one possible way to eat the maximum number of cake cells is as follows (perform 3 eats).
You are given two arrays $$$a$$$ and $$$b$$$ both consisting of $$$n$$$ positive (greater than zero) integers. You are also given an integer $$$k$$$.
In one move, you can choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) and swap $$$a_i$$$ and $$$b_j$$$ (i.e. $$$a_i$$$ becomes $$$b_j$$$ and vice versa). Note that $$$i$$$ and $$$j$$$ can be equal or different (in particular, swap $$$a_2$$$ with $$$b_2$$$ or swap $$$a_3$$$ and $$$b_9$$$ both are acceptable moves).
Your task is to find the maximum possible sum you can obtain in the array $$$a$$$ if you can do no more than (i.e. at most) $$$k$$$ such moves (swaps).
You have to answer $$$t$$$ independent test cases.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases. Then $$$t$$$ test cases follow.
The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 30; 0 \le k \le n$$$) — the number of elements in $$$a$$$ and $$$b$$$ and the maximum number of moves you can do. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 30$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$. The third line of the test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 30$$$), where $$$b_i$$$ is the $$$i$$$-th element of $$$b$$$.
For each test case, print the answer — the maximum possible sum you can obtain in the array $$$a$$$ if you can do no more than (i.e. at most) $$$k$$$ swaps.
5 2 1 1 2 3 4 5 5 5 5 6 6 5 1 2 5 4 3 5 3 1 2 3 4 5 10 9 10 10 9 4 0 2 2 4 3 2 4 2 3 4 4 1 2 2 1 4 4 5 4
6 27 39 11 17
In the first test case of the example, you can swap $$$a_1 = 1$$$ and $$$b_2 = 4$$$, so $$$a=[4, 2]$$$ and $$$b=[3, 1]$$$.
In the second test case of the example, you don't need to swap anything.
In the third test case of the example, you can swap $$$a_1 = 1$$$ and $$$b_1 = 10$$$, $$$a_3 = 3$$$ and $$$b_3 = 10$$$ and $$$a_2 = 2$$$ and $$$b_4 = 10$$$, so $$$a=[10, 10, 10, 4, 5]$$$ and $$$b=[1, 9, 3, 2, 9]$$$.
In the fourth test case of the example, you cannot swap anything.
In the fifth test case of the example, you can swap arrays $$$a$$$ and $$$b$$$, so $$$a=[4, 4, 5, 4]$$$ and $$$b=[1, 2, 2, 1]$$$.
Kefa decided to make some money doing business on the Internet for exactly n days. He knows that on the i-th day (1 ≤ i ≤ n) he makes ai money. Kefa loves progress, that's why he wants to know the length of the maximum non-decreasing subsegment in sequence ai. Let us remind you that the subsegment of the sequence is its continuous fragment. A subsegment of numbers is called non-decreasing if all numbers in it follow in the non-decreasing order.
Help Kefa cope with this task!
The first line contains integer n (1 ≤ n ≤ 105).
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).
Print a single integer — the length of the maximum non-decreasing subsegment of sequence a.
6
2 2 1 3 4 1
3
3
2 2 9
3
In the first test the maximum non-decreasing subsegment is the numbers from the third to the fifth one.
In the second test the maximum non-decreasing subsegment is the numbers from the first to the third one.
You are given two integers $$$n$$$ and $$$m$$$ ($$$m \lt n$$$). Consider a convex regular polygon of $$$n$$$ vertices. Recall that a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length).
Examples of convex regular polygons Your task is to say if it is possible to build another convex regular polygon with $$$m$$$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon.
You have to answer $$$t$$$ independent test cases.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The next $$$t$$$ lines describe test cases. Each test case is given as two space-separated integers $$$n$$$ and $$$m$$$ ($$$3 \le m \lt n \le 100$$$) — the number of vertices in the initial polygon and the number of vertices in the polygon you want to build.
For each test case, print the answer — "YES" (without quotes), if it is possible to build another convex regular polygon with $$$m$$$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon and "NO" otherwise.
2 6 3 7 3
YES NO
The first test case of the example It can be shown that the answer for the second test case of the example is "NO".
Scrooge McDuck keeps his most treasured savings in a home safe with a combination lock. Each time he wants to put there the treasures that he's earned fair and square, he has to open the lock.
The combination lock is represented by n rotating disks with digits from 0 to 9 written on them. Scrooge McDuck has to turn some disks so that the combination of digits on the disks forms a secret combination. In one move, he can rotate one disk one digit forwards or backwards. In particular, in one move he can go from digit 0 to digit 9 and vice versa. What minimum number of actions does he need for that?
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of disks on the combination lock.
The second line contains a string of n digits — the original state of the disks.
The third line contains a string of n digits — Scrooge McDuck's combination that opens the lock.
Print a single integer — the minimum number of moves Scrooge McDuck needs to open the lock.
5
82195
64723
13
In the sample he needs 13 moves:
- 1 disk:
- 2 disk:
- 3 disk:
- 4 disk:
- 5 disk:
Valera runs a 24/7 fast food cafe. He magically learned that next day n people will visit his cafe. For each person we know the arrival time: the i-th person comes exactly at hi hours mi minutes. The cafe spends less than a minute to serve each client, but if a client comes in and sees that there is no free cash, than he doesn't want to wait and leaves the cafe immediately.
Valera is very greedy, so he wants to serve all n customers next day (and get more profit). However, for that he needs to ensure that at each moment of time the number of working cashes is no less than the number of clients in the cafe.
Help Valera count the minimum number of cashes to work at his cafe next day, so that they can serve all visitors.
The first line contains a single integer n (1 ≤ n ≤ 105), that is the number of cafe visitors.
Each of the following n lines has two space-separated integers hi and mi (0 ≤ hi ≤ 23; 0 ≤ mi ≤ 59), representing the time when the i-th person comes into the cafe.
Note that the time is given in the chronological order. All time is given within one 24-hour period.
Print a single integer — the minimum number of cashes, needed to serve all clients next day.
4
8 0
8 10
8 10
8 45
2
3
0 12
10 11
22 22
1
In the first sample it is not enough one cash to serve all clients, because two visitors will come into cafe in 8:10. Therefore, if there will be one cash in cafe, then one customer will be served by it, and another one will not wait and will go away.
In the second sample all visitors will come in different times, so it will be enough one cash.
You are given array consisting of n integers. Your task is to find the maximum length of an increasing subarray of the given array.
A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray strictly greater than previous.
The first line contains single positive integer n (1 ≤ n ≤ 105) — the number of integers.
The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).
Print the maximum length of an increasing subarray of the given array.
5
1 7 2 11 15
3
6
100 100 100 100 100 100
1
3
1 2 3
3
Vasya works as a DJ in the best Berland nightclub, and he often uses dubstep music in his performance. Recently, he has decided to take a couple of old songs and make dubstep remixes from them.
Let's assume that a song consists of some number of words. To make the dubstep remix of this song, Vasya inserts a certain number of words "WUB" before the first word of the song (the number may be zero), after the last word (the number may be zero), and between words (at least one between any pair of neighbouring words), and then the boy glues together all the words, including "WUB", in one string and plays the song at the club.
For example, a song with words "I AM X" can transform into a dubstep remix as "WUBWUBIWUBAMWUBWUBX" and cannot transform into "WUBWUBIAMWUBX".
Recently, Petya has heard Vasya's new dubstep track, but since he isn't into modern music, he decided to find out what was the initial song that Vasya remixed. Help Petya restore the original song.
The input consists of a single non-empty string, consisting only of uppercase English letters, the string's length doesn't exceed 200 characters. It is guaranteed that before Vasya remixed the song, no word contained substring "WUB" in it; Vasya didn't change the word order. It is also guaranteed that initially the song had at least one word.
Print the words of the initial song that Vasya used to make a dubsteb remix. Separate the words with a space.
WUBWUBABCWUB
ABC
WUBWEWUBAREWUBWUBTHEWUBCHAMPIONSWUBMYWUBFRIENDWUB
WE ARE THE CHAMPIONS MY FRIEND
In the first sample: "WUBWUBABCWUB" = "WUB" + "WUB" + "ABC" + "WUB". That means that the song originally consisted of a single word "ABC", and all words "WUB" were added by Vasya.
In the second sample Vasya added a single word "WUB" between all neighbouring words, in the beginning and in the end, except for words "ARE" and "THE" — between them Vasya added two "WUB".
Pari has a friend who loves palindrome numbers. A palindrome number is a number that reads the same forward or backward. For example 12321, 100001 and 1 are palindrome numbers, while 112 and 1021 are not.
Pari is trying to love them too, but only very special and gifted people can understand the beauty behind palindrome numbers. Pari loves integers with even length (i.e. the numbers with even number of digits), so she tries to see a lot of big palindrome numbers with even length (like a 2-digit 11 or 6-digit 122221), so maybe she could see something in them.
Now Pari asks you to write a program that gets a huge integer n from the input and tells what is the n-th even-length positive palindrome number?
The only line of the input contains a single integer n (1 ≤ n ≤ 10100 000).
Print the n-th even-length palindrome number.
1
11
10
1001
The first 10 even-length palindrome numbers are 11, 22, 33, ... , 88, 99 and 1001.
Lenny is playing a game on a 3 × 3 grid of lights. In the beginning of the game all lights are switched on. Pressing any of the lights will toggle it and all side-adjacent lights. The goal of the game is to switch all the lights off. We consider the toggling as follows: if the light was switched on then it will be switched off, if it was switched off then it will be switched on.
Lenny has spent some time playing with the grid and by now he has pressed each light a certain number of times. Given the number of times each light is pressed, you have to print the current state of each light.
The input consists of three rows. Each row contains three integers each between 0 to 100 inclusive. The j-th number in the i-th row is the number of times the j-th light of the i-th row of the grid is pressed.
Print three lines, each containing three characters. The j-th character of the i-th line is "1" if and only if the corresponding light is switched on, otherwise it's "0".
1 0 0
0 0 0
0 0 1
001
010
100
1 0 1
8 8 8
2 0 3
010
011
100
So, the New Year holidays are over. Santa Claus and his colleagues can take a rest and have guests at last. When two "New Year and Christmas Men" meet, thear assistants cut out of cardboard the letters from the guest's name and the host's name in honor of this event. Then the hung the letters above the main entrance. One night, when everyone went to bed, someone took all the letters of our characters' names. Then he may have shuffled the letters and put them in one pile in front of the door.
The next morning it was impossible to find the culprit who had made the disorder. But everybody wondered whether it is possible to restore the names of the host and his guests from the letters lying at the door? That is, we need to verify that there are no extra letters, and that nobody will need to cut more letters.
Help the "New Year and Christmas Men" and their friends to cope with this problem. You are given both inscriptions that hung over the front door the previous night, and a pile of letters that were found at the front door next morning.
The input file consists of three lines: the first line contains the guest's name, the second line contains the name of the residence host and the third line contains letters in a pile that were found at the door in the morning. All lines are not empty and contain only uppercase Latin letters. The length of each line does not exceed 100.
Print "YES" without the quotes, if the letters in the pile could be permuted to make the names of the "New Year and Christmas Men". Otherwise, print "NO" without the quotes.
SANTACLAUS
DEDMOROZ
SANTAMOROZDEDCLAUS
YES
PAPAINOEL
JOULUPUKKI
JOULNAPAOILELUPUKKI
NO
BABBONATALE
FATHERCHRISTMAS
BABCHRISTMASBONATALLEFATHER
NO
In the first sample the letters written in the last line can be used to write the names and there won't be any extra letters left.
In the second sample letter "P" is missing from the pile and there's an extra letter "L".
In the third sample there's an extra letter "L".
One Sunday Petr went to a bookshop and bought a new book on sports programming. The book had exactly n pages.
Petr decided to start reading it starting from the next day, that is, from Monday. Petr's got a very tight schedule and for each day of the week he knows how many pages he will be able to read on that day. Some days are so busy that Petr will have no time to read whatsoever. However, we know that he will be able to read at least one page a week.
Assuming that Petr will not skip days and will read as much as he can every day, determine on which day of the week he will read the last page of the book.
The first input line contains the single integer n (1 ≤ n ≤ 1000) — the number of pages in the book.
The second line contains seven non-negative space-separated integers that do not exceed 1000 — those integers represent how many pages Petr can read on Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday correspondingly. It is guaranteed that at least one of those numbers is larger than zero.
Print a single number — the number of the day of the week, when Petr will finish reading the book. The days of the week are numbered starting with one in the natural order: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday.
100
15 20 20 15 10 30 45
6
2
1 0 0 0 0 0 0
1
Note to the first sample:
By the end of Monday and therefore, by the beginning of Tuesday Petr has 85 pages left. He has 65 pages left by Wednesday, 45 by Thursday, 30 by Friday, 20 by Saturday and on Saturday Petr finishes reading the book (and he also has time to read 10 pages of something else).
Note to the second sample:
On Monday of the first week Petr will read the first page. On Monday of the second week Petr will read the second page and will finish reading the book.
A frog is currently at the point $$$0$$$ on a coordinate axis $$$Ox$$$. It jumps by the following algorithm: the first jump is $$$a$$$ units to the right, the second jump is $$$b$$$ units to the left, the third jump is $$$a$$$ units to the right, the fourth jump is $$$b$$$ units to the left, and so on.
Formally:
- if the frog has jumped an even number of times (before the current jump), it jumps from its current position $$$x$$$ to position $$$x+a$$$;
- otherwise it jumps from its current position $$$x$$$ to position $$$x-b$$$.
Your task is to calculate the position of the frog after $$$k$$$ jumps.
But... One more thing. You are watching $$$t$$$ different frogs so you have to answer $$$t$$$ independent queries.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of queries.
Each of the next $$$t$$$ lines contain queries (one query per line).
The query is described as three space-separated integers $$$a, b, k$$$ ($$$1 \le a, b, k \le 10^9$$$) — the lengths of two types of jumps and the number of jumps, respectively.
Print $$$t$$$ integers. The $$$i$$$-th integer should be the answer for the $$$i$$$-th query.
6 5 2 3 100 1 4 1 10 5 1000000000 1 6 1 1 1000000000 1 1 999999999
8 198 -17 2999999997 0 1
In the first query frog jumps $$$5$$$ to the right, $$$2$$$ to the left and $$$5$$$ to the right so the answer is $$$5 - 2 + 5 = 8$$$.
In the second query frog jumps $$$100$$$ to the right, $$$1$$$ to the left, $$$100$$$ to the right and $$$1$$$ to the left so the answer is $$$100 - 1 + 100 - 1 = 198$$$.
In the third query the answer is $$$1 - 10 + 1 - 10 + 1 = -17$$$.
In the fourth query the answer is $$$10^9 - 1 + 10^9 - 1 + 10^9 - 1 = 2999999997$$$.
In the fifth query all frog's jumps are neutralized by each other so the answer is $$$0$$$.
The sixth query is the same as the fifth but without the last jump so the answer is $$$1$$$.
The Berland Armed Forces System consists of n ranks that are numbered using natural numbers from 1 to n, where 1 is the lowest rank and n is the highest rank.
One needs exactly di years to rise from rank i to rank i + 1. Reaching a certain rank i having not reached all the previous i - 1 ranks is impossible.
Vasya has just reached a new rank of a, but he dreams of holding the rank of b. Find for how many more years Vasya should serve in the army until he can finally realize his dream.
The first input line contains an integer n (2 ≤ n ≤ 100). The second line contains n - 1 integers di (1 ≤ di ≤ 100). The third input line contains two integers a and b (1 ≤ a < b ≤ n). The numbers on the lines are space-separated.
Print the single number which is the number of years that Vasya needs to rise from rank a to rank b.
3
5 6
1 2
5
3
5 6
1 3
11
Olga came to visit the twins Anna and Maria and saw that they have many cookies. The cookies are distributed into bags. As there are many cookies, Olga decided that it's no big deal if she steals a bag. However, she doesn't want the sisters to quarrel because of nothing when they divide the cookies. That's why Olga wants to steal a bag with cookies so that the number of cookies in the remaining bags was even, that is, so that Anna and Maria could evenly divide it into two (even 0 remaining cookies will do, just as any other even number). How many ways there are to steal exactly one cookie bag so that the total number of cookies in the remaining bags was even?
The first line contains the only integer n (1 ≤ n ≤ 100) — the number of cookie bags Anna and Maria have. The second line contains n integers ai (1 ≤ ai ≤ 100) — the number of cookies in the i-th bag.
Print in the only line the only number — the sought number of ways. If there are no such ways print 0.
1
1
1
10
1 2 2 3 4 4 4 2 2 2
8
11
2 2 2 2 2 2 2 2 2 2 99
1
In the first sample Olga should take the only bag so that the twins ended up with the even number of cookies.
In the second sample Olga can take any of five bags with two cookies or any of three bags with four cookies — 5 + 3 = 8 ways in total.
In the third sample, no matter which bag with two cookies Olga chooses, the twins are left with 2 * 9 + 99 = 117 cookies. Thus, Olga has only one option: to take the bag with 99 cookies.
Ania has a large integer $$$S$$$. Its decimal representation has length $$$n$$$ and doesn't contain any leading zeroes. Ania is allowed to change at most $$$k$$$ digits of $$$S$$$. She wants to do it in such a way that $$$S$$$ still won't contain any leading zeroes and it'll be minimal possible. What integer will Ania finish with?
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 200\,000$$$, $$$0 \leq k \leq n$$$) — the number of digits in the decimal representation of $$$S$$$ and the maximum allowed number of changed digits.
The second line contains the integer $$$S$$$. It's guaranteed that $$$S$$$ has exactly $$$n$$$ digits and doesn't contain any leading zeroes.
Output the minimal possible value of $$$S$$$ which Ania can end with. Note that the resulting integer should also have $$$n$$$ digits.
5 3 51528
10028
3 2 102
100
1 1 1
0
A number has leading zeroes if it consists of at least two digits and its first digit is $$$0$$$. For example, numbers $$$00$$$, $$$00069$$$ and $$$0101$$$ have leading zeroes, while $$$0$$$, $$$3000$$$ and $$$1010$$$ don't have leading zeroes.
After lessons Nastya decided to read a book. The book contains $$$n$$$ chapters, going one after another, so that one page of the book belongs to exactly one chapter and each chapter contains at least one page.
Yesterday evening Nastya did not manage to finish reading the book, so she marked the page with number $$$k$$$ as the first page which was not read (i.e. she read all pages from the $$$1$$$-st to the $$$(k-1)$$$-th).
The next day Nastya's friend Igor came and asked her, how many chapters remain to be read by Nastya? Nastya is too busy now, so she asks you to compute the number of chapters she has not completely read yet (i.e. the number of chapters she has not started to read or has finished reading somewhere in the middle).
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of chapters in the book.
There are $$$n$$$ lines then. The $$$i$$$-th of these lines contains two integers $$$l_i$$$, $$$r_i$$$ separated by space ($$$l_1 = 1$$$, $$$l_i \leq r_i$$$) — numbers of the first and the last pages of the $$$i$$$-th chapter. It's guaranteed that $$$l_{i+1} = r_i + 1$$$ for all $$$1 \leq i \leq n-1$$$, and also that every chapter contains at most $$$100$$$ pages.
The $$$(n+2)$$$-th line contains a single integer $$$k$$$ ($$$1 \leq k \leq r_n$$$) — the index of the marked page.
Print a single integer — the number of chapters which has not been completely read so far.
3 1 3 4 7 8 11 2
3
3 1 4 5 9 10 12 9
2
1 1 7 4
1
In the first example the book contains $$$11$$$ pages and $$$3$$$ chapters — $$$[1;3]$$$, $$$[4;7]$$$ and $$$[8;11]$$$. Nastya marked the $$$2$$$-nd page, so she finished in the middle of the $$$1$$$-st chapter. So, all chapters has not been read so far, so the answer is $$$3$$$.
The book in the second example contains $$$12$$$ pages and $$$3$$$ chapters too, but Nastya finished reading in the middle of the $$$2$$$-nd chapter, so that the answer is $$$2$$$.
Maria is the most active old lady in her house. She was tired of sitting at home. She decided to organize a ceremony against the coronavirus.
She has $$$n$$$ friends who are also grannies (Maria is not included in this number). The $$$i$$$-th granny is ready to attend the ceremony, provided that at the time of her appearance in the courtyard there will be at least $$$a_i$$$ other grannies there. Note that grannies can come into the courtyard at the same time. Formally, the granny $$$i$$$ agrees to come if the number of other grannies who came earlier or at the same time with her is greater than or equal to $$$a_i$$$.
Grannies gather in the courtyard like that.
- Initially, only Maria is in the courtyard (that is, the initial number of grannies in the courtyard is $$$1$$$). All the remaining $$$n$$$ grannies are still sitting at home.
- On each step Maria selects a subset of grannies, none of whom have yet to enter the courtyard. She promises each of them that at the time of her appearance there will be at least $$$a_i$$$ other grannies (including Maria) in the courtyard. Maria can call several grannies at once. In this case, the selected grannies will go out into the courtyard at the same moment of time.
- She cannot deceive grannies, that is, the situation when the $$$i$$$-th granny in the moment of appearing in the courtyard, finds that now there are strictly less than $$$a_i$$$ other grannies (except herself, but including Maria), is prohibited. Please note that if several grannies appeared in the yard at the same time, then each of them sees others at the time of appearance.
Your task is to find what maximum number of grannies (including herself) Maria can collect in the courtyard for the ceremony. After all, the more people in one place during quarantine, the more effective the ceremony!
Consider an example: if $$$n=6$$$ and $$$a=[1,5,4,5,1,9]$$$, then:
- at the first step Maria can call grannies with numbers $$$1$$$ and $$$5$$$, each of them will see two grannies at the moment of going out into the yard (note that $$$a_1=1 \le 2$$$ and $$$a_5=1 \le 2$$$);
- at the second step, Maria can call grannies with numbers $$$2$$$, $$$3$$$ and $$$4$$$, each of them will see five grannies at the moment of going out into the yard (note that $$$a_2=5 \le 5$$$, $$$a_3=4 \le 5$$$ and $$$a_4=5 \le 5$$$);
- the $$$6$$$-th granny cannot be called into the yard — therefore, the answer is $$$6$$$ (Maria herself and another $$$5$$$ grannies).
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then test cases follow.
The first line of a test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of grannies (Maria is not included in this number).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$).
It is guaranteed that the sum of the values $$$n$$$ over all test cases of the input does not exceed $$$10^5$$$.
For each test case, print a single integer $$$k$$$ ($$$1 \le k \le n + 1$$$) — the maximum possible number of grannies in the courtyard.
4 5 1 1 2 2 1 6 2 3 4 5 6 7 6 1 5 4 5 1 9 5 1 2 3 5 6
6 1 6 4
In the first test case in the example, on the first step Maria can call all the grannies. Then each of them will see five grannies when they come out. Therefore, Maria and five other grannies will be in the yard.
In the second test case in the example, no one can be in the yard, so Maria will remain there alone.
The third test case in the example is described in the details above.
In the fourth test case in the example, on the first step Maria can call grannies with numbers $$$1$$$, $$$2$$$ and $$$3$$$. If on the second step Maria calls $$$4$$$ or $$$5$$$ (one of them), then when a granny appears in the yard, she will see only four grannies (but it is forbidden). It means that Maria can't call the $$$4$$$-th granny or the $$$5$$$-th granny separately (one of them). If she calls both: $$$4$$$ and $$$5$$$, then when they appear, they will see $$$4+1=5$$$ grannies. Despite the fact that it is enough for the $$$4$$$-th granny, the $$$5$$$-th granny is not satisfied. So, Maria cannot call both the $$$4$$$-th granny and the $$$5$$$-th granny at the same time. That is, Maria and three grannies from the first step will be in the yard in total.