Description

Princess Twilight Sparkle's birthday is around the corner. As a good friend of Twilight, the best party pony Pinkie Pie decides to throw a birthday party for her! Pinkie plans to invite n  ponies to join this big party. At the beginning of the party, Pinkie will give away a bunch of balloons, and here's how it will work :

First, all ​ ponies, labelled from 1 to n, will sit in a circle. Pinkie will then give away three different colors of balloons -- red, blue and yellow. For each color, Pinkie will randomly choose a number x​. Counting begins at the pony labelled 1 and proceeds around the circle. After skipping x​ ponies, Pinkie will give that pony a balloon. The whole round stops when any pony could get two same balloons, and Pinkie won't give that pony the same balloon again. That is, there are three round of giveaway in total, and each pony will get three different colors of balloons at most.

For example, if there are 6 ponies in the party:

The first time Pinkie choose x = 2 and gives red balloons, so ponies labelled 2, 4 and 6 will get red balloons.

The second time Pinkie choose x = 3 and gives blue balloons, so ponies labelled 3 and 6 will get blue balloons.

The last time Pinkie choose x = 5 and gives yellow balloons, so all ponies will get yellow balloons.

(The order of getting the yellow balloons is : 5, 4, 3, 2, 1, 6)

Pinkie is wondering how many ponies will get three different kinds of balloons, so she can prepare for the following game she wants to play in the party. If you can help Pinkie, maybe she will teach you how to make a mouth-watering cupcake.

Input

First line contains one integer ​T, representing the number of testcases (or the parties Pinkie will throw, who doesn't like parties?).

The next T lines contains four integers n, x₁, x₂, x₃, representing the number of ponies who are invited to the party, and the three random number Pinkie chooses in the party.

• ​1 ≤ T ≤ 10

• Testcase #1 ~ #4 : 1 ≤ x₁, x₂, x₃ ≤ n ≤ 10⁵

• Testcase #5 : 1 ≤ x₁, x₂, x₃ ≤ n ≤ 10¹⁸

Output

For each testcase (party), please output a line contains one integer representing the number of ponies who get three balloons.

(i.e. Please print '\n' after each answer.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Knuckles, from Ugandan, is finding his queen. He accidentally find a ancient stele which curved two numbers on it. He reckon it as a clue to find his queen. Knuckles is very smart. He soon realizes that the rule between numbers.

The stele contains two numbers l,r which means the range from l ~ r .

Knuckles wants to find two different numbers x,y in the range, 

in other word l <= x < y <= r.

And Knuckles also wants that x divides y( y%x == 0 ). 

Knuckles thinks that the minimum sum of x+y will be the clue to find the queen. Because the stele is from Ugandan gods there is always an answer.

Help Knuckles find his queen or he will spit on you.

Input

input contains two integer l and r ( 1 <= l < r <= 10⁹ )

Output

output contains two integer x and y ( l <= x < y <= r ) which x divides y.( remember print \n at the end of output and x ,y are seperated by a blank.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas wants to eat watermelon. But the watermelons are stored in a cylindrical(圓柱狀) box.

He has n watermelons and each one has a specific index denote as a_i.

Osas wants to eat a watermelon indexed a_i.

But if the watermelon indexed a_i is not on the top,

he needs to eat all watermelon above the watermelon indexed a_i.

Osas also has a list which is the order of watermelons he wants to eat which denoted as b_i.

The length of the list is also n and all b_i are distinct.

Please help him calculate that each time he wants to eat a watermelon, how many watermelons he needs to eat at same time?

For example ：

if the index of watermelon from top to bottom is: 5, 3, 2, 1, 4. And the list Osas has is: 2, 3, 4, 5, 1.

First time Osas will eat 3 watermelons(5,3,2).

Second time because the watermelons that indexed 3 is already been eaten, Osas eat 0 watermelon . So on and so forth.

In this example, you need to output: 3 0 2 0 0.

Input

input contains three lines.

First line contains n the number of watermelons.( 1 <= n <= 2*10⁵ )

Second line contains n integer a₁ ~ a_n which denote as the index of watermelons from top to bottom .( 1 <= a_i <= n )

Third line contains n integer b₁ ~ b_n which denote as the order of watermelons  that Osas' wants to eat.( 1 <= b_i <= n )

Output

output contains one line.

output n integer means the number of watermelons that each time Osas eat. Separate each number by a blank but don't print the blank after the last number.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Johnny is a three years old kid. He likes to eat sugar. One day, he sneaked into the kitchen in order to grab some sugar to eat. Unfortunately, his papa catched him.

His papa called him: " Johnny, Johnny! "

Johnny replied: " Yes, papa. "

papa then asked: " Eating sugar? "

Johnny lied: " No, papa. "

At that moment, Johnny began to think that what's defintion of string equivalent?

Johnny thinks that string a and string b is equivalent if a and b are the same or string a and string b can be devided into two same size part: a₁, a₂, b₁, b₂ and the following rules fulfill：

(  ( a1 == b1 ) && ( a2 == b2 ) )  or  ( ( a1 == b2 ) && ( a2 == b1 ) )

In above sentence, "==" means whether a and b are the same or string a and string b can be devided into two same size part: a₁, a₂, b₁, b₂ and the following rules fulfill: (  ( a1 == b1 ) && ( a2 == b2 ) )  or  ( ( a1 == b2 ) && ( a2 == b1 ) ). You can consider this equal definition as a recursion.

For example: 

a = " papa ", b = " apap ", we need to check if " pa " equals " ap " in Johnny ' s rule.

Therefore, we divide " pa " into "p" and "a", and divide "ap" into "a" and "p". 

Then, because "p" == "p" && " a " == "a", we know that "pa" == "ap".

Hence, we can conclude that " papa " equals " apap ".

Note that we can't divide a string if the length of the string is an odd number.

Help Johnny find out whether the two string are the same. If you help him, he will give you some sugar.

Input

input contains two lines.

First line is the string a. 

Second line is the string b. 

the length of the two string are the same and the length is from 1~10⁵ ( 1 <= length <= 10⁵ )

Output

output contains one line.

print "YES" if two string is equal in Johnny's rule,

print "NO" otherwise.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two number a,b.

You need to calculate how many 1 appear in range a~b(decimal representation).

Example:

Given a = 1, b = 11.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

There're four 1 appear in range 1~11(1, 10, 11).

The answer is 4.

Input

First line contains one integer t(1 <= t <= 10^6) which means the number of testcases.

The following t lines, each line contains two integer a, b( 1 <= a <= b <= 10^6)

Output

For each testcase print only one number which means the number of 1 appear in range a~b.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1. Only C only allowed. Solving problems with other languages (e.g. python, java) are forbidden, otherwise you'll get zero point.

2. Paper references, electronic devices, or other items that may contain any information relative to this exam are not allowed.

3. Before leaving, please tell TAs, we'll check if your accepted / partially accepted submissions are all written in C . After you pass the check, you may sign your name as a record and leave.

4. The score of each problem is shown below:

   • 11618: 7 points

   • 12133: 5 points

   • 12132: 5 points

   • 12678: 9 points

   • 12129: 9 points

If you get partially correct in a problem, your score of the problem will be

• score of the problem * number of testcases you passed / number of testcases

For example, if score of a problem is 10 points and the problem contains 6 testcases. If you pass the 3 testcases, you'll get 10*3/6=5 points on this problem.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss