Nate is tired of 2D girls and has decided that this year he will try looking for the real thing. Although Nate is too shy to go out and talk to one, he realized he could avoid having to go through the ordeal of real-life interaction by writing an anonymous tegami (letter) to his prospective 3D girl. He can do this by cutting up letters from his old Pokémon trading cards.
However, as much as Nate would be happy with any living, breathing 3D girl, he still wants someone with substance. To provide the recipient with a challenge, he decided to encrypt his letter using a simple cipher.
Nate will think of a number $$$k$$$ which is the number of times he will shift the alphabet to the left. For example, if Nate chooses $$$k=3$$$, then the alphabet [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z] is transformed to [d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, a, b, c].
This transformed alphabet is what he uses to write the tegami.
Help Nate determine if he was able to obtain enough letters from his $$$n$$$ trading cards to write the tegami if each letter can only be used once.
The first line of input contains three space-separated integers $$$n$$$, $$$m$$$, and $$$k$$$, respectively. The first number, $$$n$$$, is the number of words Nate cut out. The second number, $$$m$$$, is the number of words in the tegami. The third number, $$$k$$$, is the number of times the alphabet is shifted, respectively.
The second line of input contains $$$n$$$ space-separated strings, the words Nate cut out.
The third line of input contains $$$m$$$ space-separated words consisting only of lowercase English letters, the message that Nate wants to encrypt and send to his potential 3D girl.
Constraints
$$$1 \le n \le 100$$$
$$$1 \le m \le 100$$$
$$$0 \le k \le 100$$$
The sum of the lengths of the words Nate cut out will not exceed $$$10^{5}$$$.
The sum of the lengths of the words in the message Nate wants to encrypt will not exceed $$$10^{5}$$$.
Output Make her kokoro go doki-doki! if Nate has enough letters to write the encrypted tegami, and It is gonna be daijoubu. if Nate doesn't have enough letters.
4 3 3 chikorita vulpix pidgeot quagsire date me please
It is gonna be daijoubu.
6 9 22 joltik zapdos kangaskhan pelipper cyndaquil qwilfish will you go to under the stars with me
Make her kokoro go doki-doki!
In the second example, the alphabet is shifted $$$k = 22$$$ characters to the left as shown below:
Before: a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
After: w, x, y, z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v
Using this new alphabet, the message is encrypted into sehh ukq ck pk qjzan pda opwno sepd ia.
Nate can write the word sehh using the letter s from the kangaskhan card, a letter e from the pelipper card, the letter h from the qwilfish card, and the letter h from the kangaskhan card.
Notice that different letters may come from the same card, but each letter may only be used once. He could've also used the zapdos card instead of the kangaskhan card for the letter s. If you continue this process you will find that he has enough characters to write the entire tegami.
Nate loves dinosaurs very much due to the influence of the anime and card game Dinosaur King in his childhood. Recently, he has been collecting many variants of the new craze called "Fossilites," dinosaurs in bone/fossil form. He is very much in love with them and plays with them everyday, hence his nickname "Bones." One day, Nate discovered something horrible. While at school, his little brother played with his Fossilites! His younger brother took his dinosaurs apart and tried to fit the different bones to different bodies. His mom cleaned up the mess by just placing piles of bones into $$$n$$$ different boxes such that each box contains $$$m$$$ different bones.
Nate decides to focus on finding the bones of his favorite dinosaur first. Luckily, there is a way for Nate to identify them. His favorite dinosaur has weight $$$x$$$. A bone with length $$$l$$$ belongs to his favorite dinosaur if and only if $$$l$$$ and $$$x$$$ share a common factor besides $$$1$$$. That is to say, there exists an integer $$$d \gt 1$$$ such that both $$$l$$$ and $$$x$$$ are divisible by $$$d$$$. He can get each bone and use math to help him out. He is not patient with numbers, however, so help Nate check if he is correct through a program.
Help Nate check if he got all the bones for the dinosaur by finding the total number of bones that belong to his favorite dinosaur.
The first line of input contains three space-separated integers $$$n$$$, $$$m$$$, and $$$x$$$, respectively. The first integer, $$$n$$$, is the number of boxes. The second integer, $$$m$$$, is the number of bones per box. The third integer, $$$x$$$, is the dinosaur's weight.
The next $$$n$$$ lines of input each contain $$$m$$$ space-separated integers corresponding to a bone's length $$$l_i$$$.
Constraints
$$$1 \leq n,m \leq 100$$$
$$$2 \leq l_i \leq 10^5$$$
$$$2 \leq x \leq 10^5$$$
Output a single integer, the total number of bones that belong to dinosaur $$$x$$$.
2 3 12
5 7 6
29 12 20
3
5 5 100
11 2 3 4 5
1000 2000 3000 4000 5000
21 1222 99 83 75
921 182 27 40 284
6474 301 734 1000 990
17
In the first case: the factors of $$$12$$$ are $$$1,2,3,4,6,12$$$. In the first box, only $$$6$$$ is divisible by one of those other than $$$1$$$. In the second box, both $$$12$$$ and $$$20$$$ are divisible by one of the factors. The total number of correct bones is $$$3$$$.
In the second case: the factors of $$$100$$$ are $$$1,2,4,5,10,20,25,50,100$$$. In the first box, $$$2$$$, $$$4$$$, and $$$5$$$ are divisible by a factor of $$$100$$$. In the second box, all numbers are divisible. In the third box, $$$1222$$$ and $$$75$$$ are divisible. In the fourth box, $$$182$$$, $$$40$$$, $$$284$$$ are divisible. In the fifth and last box, all numbers apart from $$$301$$$ are divisible. The total number of correct bones is $$$17$$$.
Nate wants to have more people join his contest. However, he doesn't have much time. He can only directly send invitations to $$$k$$$ people. Thankfully, if he invites someone, that person can tell all of his friends about the contest, and those friends can tell all of their friends, and so on.
Suppose that there are $$$n$$$ people and $$$m$$$ pairs of them are friends. What is the maximum number of people he can invite?
The first line of input contains three space-separated integers $$$n$$$, $$$m$$$, and $$$k$$$, respectively. The first integer, $$$n$$$, is the number of people. The second integer, $$$m$$$, is the number of pairs of friends. The third integer, $$$k$$$, is the number of invitations Nate can directly send.
The next $$$m$$$ lines of input each contain two space-separated strings, the names of a pair of friends. Each name is composed of only lowercase English letters and doesn't exceed 10 letters in length.
Constraints
$$$1 \le n \le 10^5$$$
$$$1 \le m \le 10^5$$$
$$$1 \le k \le \min\left(n, 100\right)$$$
Output a single integer, the maximum number of people Nate can invite.
3 2 1 Anne Billy Anne Charles
3
6 4 1 Dave Earl Earl Fontana Gillian Heather Heather Ian
3
6 3 3 Joshua Karla Lily Mark Ned Oliver
6
In the first test case, Nate can invite Anne, who invites both her friends Billy and Charles.
In the second test case, Nate can invite Dave, who invites Earl, who invites Fontana. There is no way to invite all six people, as none of Dave, Earl, and Fontana are friends with Gillian, Heather, or Ian.
In the third test case, Nate can invite Joshua, Lily, and Ned, who then invite Karla, Mark, and Oliver respectively.
One Wednesday evening, Nate went out drinking milk tea with his friends, spending $$$x$$$% of his money on that day.
On Thursday, he checked his wallet and watched in confusion as $$$y$$$% of his money vanished before his very eyes!
He then remembers that on Tuesday, a similar event transpired as he checked his wallet and watched money magically appear in his wallet!
Realizing that the amount of money that appeared in his wallet on Tuesday is the exact same amount that he lost on Thursday, he deduced that the portion of money he lost on Thursday somehow went back in time and got transferred to his wallet on Tuesday!
This makes managing his finances confusing, and so he wants your help.
If he had $$$n$$$ Philippine pesos in his wallet on Monday, how much money would he have on each of the five weekdays this week?
The input consists of a line containing three space-separated integers $$$n$$$, $$$x$$$, and $$$y$$$. The first integer, $$$n$$$, is the amount of money he had on Monday. The second integer, $$$x$$$, is the percentage of money in his wallet he had spent on Wednesday. The third integer, $$$y$$$, is the percentage of money in his wallet on Thursday that got sent back in time.
Constraints
$$$1 \leq n \leq 10^{8}$$$
$$$1 \leq x \leq 100$$$
$$$1 \leq y \leq 100$$$
Output five space-separated integers: the amount of money Nate had on Monday, Tuesday, Wednesday, Thursday, and Friday, in that order.
The answer will be accepted if it is within $$$10^{-4}$$$ of the correct answer.
100 50 50
100.0000 133.3333 66.6667 33.3333 33.3333
100 25 25
100.0000 123.0769 92.3077 69.2308 69.2308
Nate has $$$3$$$ special types of torches, with colors red, blue, and yellow that combines colors subtractively and not additively. The colors mentioned, as Nate had learned in grade school, are the primary colors. When the light from the primary torches overlap, they have the following behavior:
- When red light overlaps with blue light, it produces violet.
- When blue light overlaps with yellow light, it produces green.
- When red light overlaps with yellow light, it produces orange.
When an area is affected by two torches of the same color, the color is amplified in that area. Let's call the number of torches that give the same color to an area as the power. Light becomes secondary color if and only if the two colors that affect the area are of the same power.
Now, when things get more complicated than the secondary colors, the lights get confused. Normally, when we mix violet paint with red paint, we get the color red-violet. But this is not so for the light from Nate's torches. Let's put another torch in an area affected by one of the secondary colors. If that torch is one of the component colors of the secondary color in the area, the mixed light becomes pink. But when the torch is not one of the component colors, the mixed light becomes brown.
Nate places $$$k$$$ of these torches in a field of $$$m \times n$$$ grid. Each tile of the grid is labeled with coordinate $$$(x, y)$$$, from the upper-left hand corner, whose coordinate is $$$(1, 1)$$$. Each torch has a color, denoted by RED, BLUE, and YELLOW.
When placed in a field, the torch lights up a square area of side length $$$s$$$ with the torch being in the center of that square. Let us call the side length the range. The location of the $$$i$$$th of the $$$k$$$ torches, with color $$$c_i$$$, is denoted by $$$(x_i, y_i)$$$. If the range of the torch is odd, then $$$(x_i, y_i)$$$ corresponds to the center tile of the square area lit up by the torch. If the range of the torch is even, then $$$(x_i, y_i)$$$ corresponds to the upper-left tile of the four center tiles of the square area lit up by the torch. The torch itself is placed in the middle of the four center tiles. Refer to the diagram below for a visualization. It is guaranteed that no two torches are placed in the exact same location, because that would be violating Pauli's Exclusion Principle. Nate wants to find out how many tiles inside the $$$m \times n$$$ grid are lit up with the color $$$c$$$.
The first line of input contains three space-separated integers $$$m$$$, $$$n$$$, and $$$k$$$, respectively. The first integer, $$$m$$$, is the horizontal length of the grid. The second integer, $$$n$$$, is the vertical length of the grid. The third integer, $$$k$$$, is the number of torches Nate will place. The next line of input contains $$$c$$$, the color that Nate wants. It is guaranteed that $$$c$$$ is one of the following: RED, BLUE, YELLOW, GREEN, ORANGE, VIOLET, BROWN, PINK. Each of the next $$$k$$$ lines of input contains four space-separated integers $$$c_i$$$, $$$x_i$$$, $$$y_i$$$, and $$$s$$$, respectively. The first integer, $$$c_i$$$, is the color of the torch placed. The second integer, $$$x_i$$$, is the $$$x$$$-coordinate of the center tile. The third integer, $$$y_i$$$, is the $$$y$$$-coordinate of the center tile. The fourth integer, $$$s$$$, is the side length of the square region that the torch lights up. It is guaranteed that $$$c_i$$$ is one of RED, BLUE, and YELLOW.
Constraints
$$$1 \lt m, n \leq 50 $$$
$$$1 \leq k \leq m \times n$$$
$$$1 \leq x_i \leq m$$$
$$$1 \leq y_i \leq n$$$
$$$1 \leq s \leq 50$$$
Output a single integer, the number of tiles that are lit up as the color $$$c$$$.
2 2 1 RED RED 1 1 1
1
2 2 2 BLUE RED 1 1 2 BLUE 1 1 1
0
2 2 1 RED RED 2 2 2
1
In the first test case, the red torch has a range of $$$1$$$. It is placed in the middle of the $$$(1, 1)$$$ tile.
In the second test case, the red torch has a range of $$$2$$$. The upper-left tile of the four center tiles is $$$(1, 1)$$$. The red torch is placed accordingly. The blue torch has a range of $$$1$$$, placed in the middle of the $$$(1, 1)$$$ tile. The red and the blue in the $$$(1, 1)$$$ tile overlaps, making the $$$(1, 1)$$$ tile color violet.
In the third test case, the red torch has a range of $$$2$$$. The upper-left tile of the four center tiles is $$$(2, 2)$$$. The red torch is placed on the corner of the field. Since we are only interested in the number of tiles lit with red light within the $$$2 \times 2$$$ field, the answer is $$$1$$$.
Nate is attending a meet-and-greet for his favorite celebrity voice actress, Hana Kanazawa! You might know her from her voice-over work in the Mono Guitar Hero series, Doreimon, its sequel Durararaemon, and of course, Angel Beats Agents. She announced that she would give a signed copy of her new album to whomever could guess the serial number on Volume $$$x$$$ of her favorite manga.
Nate, of course, knows that this would be the volume of The World Dog Only Knows that introduces the character Shiori, whom she voices in the anime. He also happens to know that for this series, the serial number of Volume $$$n$$$, $$$s_n$$$, satisfies the following:
- The pilot, Volume $$$0$$$, has a serial number of $$$0$$$.
- The very first volume, Volume $$$1$$$, has a serial number of $$$1$$$.
- The serial number of every volume after the first is calculated as $$$s_n = 2 s_{n-1} - s_{n-2}$$$.
Here, $$$s_{n-1}$$$ is the serial number of Volume $$$n-1$$$ and $$$s_{n-2}$$$ is the serial number of Volume $$$n-2$$$.
Nate can't think well under pressure, and a signed album from his favorite celebrity is in jeopardy! Can you help him find the serial number of Volume $$$x$$$?
The input consists of a line with only a single integer $$$x$$$, the volume whose serial number must be found.
Constraints
$$$1 \le x \le 10^{18}$$$
Output a single integer, the serial number of Volume $$$x$$$.
1
1
2
2
The serial number of Volume $$$1$$$ is given from the definition. The serial number of Volume $$$2$$$ is $$$2s_1-s_0=2$$$.
Nate found a game under his bed! He was not familiar with it, so he decided to load it in his game console. When the game finally started, Nate was greeted with the title screen, "AttAck on Eoten!" Nate was excited because this was his favorite cartoon! He was excited for an action-packed game with a compelling story. Strangely though, it seems like the models were all off. The giants, which were supposedly humanoid, now look like triangles!
Although Nate was slightly disappointed, he still pushed through with the game. After playing for $$$420$$$ minutes, he forgot they were giants so he just simply called them as triangles.
The mechanics of the game is fairly simple. Nate was stationed in a castle on the leftmost of the screen and he had to shoot with his gun to destroy triangles. The game is fairly old, so he could only shoot in a horizontal trajectory. He also noticed that hitting even just the border of a triangle would destroy it. After playing for $$$6969$$$ minutes, he noticed that the game was lazily coded: some triangles were overlapping.
After playing for $$$42069$$$ minutes, he got a sniper rifle with exactly $$$1$$$ piercing shot. A piercing shot can shoot through any number of triangles as long as they all intersect the line of fire. Nate was pretty tired already, and he just wants to shoot as many triangles in one shot. Since there were a lot of triangles on the screen, he could not determine how many he could shoot at once. Can you help him find the maximum number of triangles he can shoot in one shot?
The first line of input contains a single integer $$$n$$$, the number of triangles.
The next $$$n$$$ lines of input each contain six space-separated integers, $$$x_0,y_0,x_1,y_1,x_2,y_2$$$, respectively, where $$$(x_0,y_0),(x_1,y_1),(x_2,y_2)$$$ are the three vertices of a triangle. It is guaranteed that the triangles are non-degenerate, i.e. the three points of each triangle are not collinear.
Constraints
$$$1 \leq n \leq 142069$$$
$$$-1000000 \leq x_0,y_0,x_1,y_1,x_2,y_2 \leq 1000000$$$
Output a single integer, the maximum number of triangles Nate can hit.
1 0 6 -5 1 6 -8
1
2 0 4 -10 7 6 9 -2 -2 -6 -9 3 -7
1
5 -3 5 -8 2 -5 7 1 -5 3 -7 5 0 1 4 2 6 5 5 -2 -3 -3 3 -5 -2 1 -1 2 1 -1 2
3
For the third test case, the input would look like this. Nate can hit $$$3$$$ triangles by shooting his rifle as in the red line in the figure. There are other ways for Nate to hit $$$3$$$ triangles, but Nate cannot hit more than $$$3$$$ triangles in one shot.
It's Nate's first day in High School, and he's really nervous! Nate hopes that High School will be great, full of antics and wacky adventures, field trips and tournaments, beach episodes and kawaii demons, just like what he's seen on anime (which he's sure is a realistic and not-at-all romanticized portrayal of High School). Most of all, he hopes to find his nakama.
Whatever a nakama is, in Nate's High School class, there can be one or more nakamas, depending on the friendships within the class. Two students in the class can either be friends, or not be friends. Friendship is mutual: if student $$$A$$$ is friends with student $$$B$$$, then student $$$B$$$ is also friends with student $$$A$$$. Two students are part of the same nakama if they are friends. If a student is not friends with anyone else in the class, they also count as one nakama.
The nakama rating of a class is the number of distinct nakama present in the class.
Nate uses the timeline powers he got from watching Steins;Gate to examine every possible way the people in his class could be friends with one another. Two timelines are considered different if there exists at least one pair of students who are friends in one timeline and not friends in the other. What is the sum of the nakama ratings of a class of $$$n$$$ students across all possible different timelines?
The input consists of a line with a single integer $$$n$$$, the number of students in the class.
Constraints
$$$1 \leq n \leq 3000$$$
Output a single integer, the sum of all the nakama ratings of a class with $$$n$$$ students across all possible different timelines. Since the answer can get quite large, output its positive remainder when it is divided by $$$10^9+7$$$, a prime number.
3
13
41
680415236
Suppose there are $$$N=3$$$ students in the class: Nate, Ayumi, and Jotaro. Illustrated below are all $$$8$$$ possible ways the class could be friends, and the nakama rating of each possibility.
In case (a), there are no friendships between anyone in the class, so each student counts as one nakama. Therefore, the nakama rating for this possibility is $$$3$$$.
In cases (b), (c), and (d), two of the students in the class are friends with each other, forming one nakama. The remaining student, who isn't friends with anyone, counts as another nakama. Therefore, the nakama rating for each of these possibilities is $$$2$$$.
In cases (e), (f), (g) and (h), all of the students belong to the same nakama, so the nakama rating for each of these possibilities is $$$1$$$. For example, in case (e), since Nate and Ayumi are friends, they belong to the same nakama. Since Nate and Jotaro are also friends, they also belong to the same nakama, hence Ayumi and Jotaro also belong to the same nakama.
The sum of the Nakama Ratings across all $$$8$$$ possibilities is $$$3+2+2+2+1+1+1+1=13$$$.
Translator's Note: What is a nakama? Well, it's a really deep word that means a group of closest friends (like in One Piece) and there really is no English equivalent to how powerful that word is, so Nate has decided to keep it untranslated. The untranslated definition of nakama is: 仲間 — 1. 一緒に物事をする間柄。また、その人。2.地位・職業などの同じ人々。3. 同じ種類のもの。同類。4. 近世、商工業者の同業組合。官許を得たものを株仲間といった。(デジタル大辞泉（小学館）より). You do not need to understand this definition to solve this problem.
Nate's math teacher thinks he watches too much anime and not enough time studying for their algebra test. Nate insists that he's already prepared for the test, but in order to prove it, he has to solve the following problem that his teacher gave him.
Given $$$a$$$, $$$n$$$, and that $$$x^2 - ax + 1 = 0$$$, find $$$b$$$ such that $$$x^{2n} - bx^n + 1 = 0$$$.
The first line of input contains a single integer $$$T$$$, the number of test cases. The next $$$T$$$ lines of input each contain two space-separated integers $$$a$$$ and $$$n$$$, respectively, the values in the equation.
Constraints
$$$1 \leq T \leq 10^5$$$
$$$\left|a\right|, \left|n\right| \leq 10^{18}$$$
For each of the $$$T$$$ test cases, output in its own line a single integer, $$$b$$$, that satisfies the equation. Since the answer can get quite large, output only the positive remainder when $$$b$$$ is divided by $$$10^9+7$$$, a prime number. It can be proven that $$$b$$$ is always an integer.
3 2 1231 2 10000000 5 0
2 2 2