Description

Source : ACM International Collegiate Programming Contest Asia Regional Contest, Tsukuba, 2016/10/16 

You are given an ordered sequence of integers, (1,2,3,...,n). Then, a number of requests will be given. Each request specifes an integer in the sequence. You need to move the specied integer to the head of the sequence, leaving the order of the rest untouched. Your task is to find the order of the elements in the sequence after following all the requests successively.

Sample Output Explanation : In Sample Input 1, the initial sequence is (1; 2; 3; 4; 5). The first request is to move the integer 4 to the head, that is, to change the sequence to (4; 1; 2; 3; 5). The next request to move the integer 2 to the head makes the sequence (2; 4; 1; 3; 5). Finally, 5 is moved to the head, resulting in (5; 2; 4; 1; 3).

Input

The input consists of a single test case of the following form.

n m

e₁

:

e_m

The integer n is the length of the sequence ( 1 <= n <= 200000 ). The integer m is the number of requests ( 1 <= m <= 100000 ). The following m lines are the requests, namely e₁,...,e_m, one per line. Each request e_i ( 1 <= i <= m ) is an integer between 1 and n, inclusive, designating the element to move. Note that, the integers designate the integers themselves to move, not their positions in the sequence.

Output

Output the sequence after processing all the requests. Its elements are to be output, one per line, in the order in the sequence.

There should be a new line at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A famous streamer once said: " Abortion Uncle!! Begin abort!!! " The Abortion Uncle is also known as "The Big Hammer Rise". The famous streamer wants to know the exactly time "Big Hammer Rise" kill an enemy. Because he got a double kill, he know exacly two time which denote as a, b.

The famous streamer will give you two number a,b which are represented as float numbers and have two digit after the decimal point.

For example：

If a,b are ranged from 1~99, 1<= a , b < 100;

a,b will be like these forms： 18.00,  99.30,  71.22

You need to calculate ans = a*b, and ans should follow the rule:

if the number of digits after decimal point is less then four digits, then you need to print 0 to make it four digits.

For example: 18.56 -> 18.5600, 18 -> 18.0000, 18.9 -> 18.9000

If you tell him the right answer he will help you kill the ice bird.

( Note: you can use scanf("%d.%d %d.%d", &int, &int, &int, &int). Use %f may cause trouble because the precision of float type. )

( Note: you can use  printf("%d.%04d\n", int/10000, int%10000); )

Input

input only contains two float number a,b ( 1<= a , b < 100 ) the two number are seperated by a blank.

Output

output contains only a float number which have four digit after the decimal point.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

PaPa suspected that Johnny ate the sugar, yet Johnny said he hadn't eaten it.

Therefore, PaPa asked: " Telling lies? "

Johnny replied: " No PaPa. "

PaPa then demanded: " Open your mouth! "

Johnny laughed embarrassedly: " Ha Ha Ha!!! "

PaPa is so furious with Johnny telling lies, so he punished Johnny to do some math.

PaPa gave Johnny n numbers a₁ ~ a_n and a number k.

PaPa asked Johnny to calculate how many ways he could pick some numbers from a₁ to a_n in order to make their sum equal to k?

For example:

Given n = 5 and numbers are { 1,2,3,3,3 }, and k = 3, the answer is 4.

(Note that although there are three identical "3", we still consider them as different indentities.) { (1, 2), (3), (3), (3) }

Johnny is a bad boy, so he commands you to do this for him!

Input

Input contains two lines.

First line contains two integer n ( 1 <= n <= 20 ), k ( 1<=  k <=10⁹)

Second line contains n integer a₁ ~ a_n ( 1 <= a_i <= 10⁷ )

Output

Output only contains one integer that is sum of available ways to pick numbers, which summation is equal to k.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas accidentally found an undiscovered tomb. He successfully sneaked in without triggering any traps. When he finally got into the treasure room, he found a note that warns tomb raiders about the trap in the treasure room. Osas arranged the note and concluded some rules:

 - The treasure room has n treasure crates, each crate has its value. The values are sorted in descending order.

 - There are several intervals [l,r] on the note.

 - Tomb raiders must loot less than or equal to m treasure crates in the correct interval, where m is a number that Osas have to guess.

 - If any tomb raider loot more than m treasure crates or loot any crate that not in the interval, the trap would trigger and kill that tomb raider! Osas doesn't want to die here.

Osas wants these treasures, but he doesn't want to die. Osas wants to know if he pick one interval and guess a number as "m", what is the maximum value he could loot? Osas asks you for help!

Osas will give you the value of every treasure crate and the number he would like to guess, you need to write a program to help him.

Input

The input contains exactly one testcase.

The first line contains two integers n, q. q indicates the amount of queries of (l,r,m).

The next line is the sequence of values of n treasure crates, each seperated by a space. 

The next q lines, each line contains exactly three integers l, r, m.

1<=m<=n<=10⁶, 1<=q<=10⁶, 1<=l<=r<=n, m<=r-l+1, the value of every treasure crate won't larger than 10⁵ or smaller than -10⁵. All of the values are integers. Notice that the value could be negative, and Osas can choose nothing.

Note that the sequence index starts from 1. For example: for a sequence "a": "3 4 5 6 7", a[4]=6, a[1]=3.

Output

For each query, output the maximum value Osas could get. Each query holds exactly one line.

Remember to print a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are n children in Johnny Johnny' s family.

And number i child wants to have a_i units of sugar.

But their PaPa don't want them eat too much sugar. Therefore he will randomly choose some children and only give them the great common divisor of a_i. 

For example, if there're n=5 children and a_i = { 1, 4, 6, 7, 18 }.

Suppose PaPa choose the children numbered 2,3,5.

Then all children will only get  gcd(a₂, a₃, a₅) = gcd(4,6,18) = 2 unit of sugar.

Now Johnny wants to know what's the maximum amount of sugar they can get.(PaPa will at least choose two child) 

If you can help him, he will laugh at you for you don't have any sugar " Ha Ha Ha!!! "

To calculate great common divisor, you can use the method 輾轉相除法(https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)

Input

input contains two lines.

First line only contains one integer n ( 2 <= n <=  1000)

Second line contain n integers a₁ ~ a_n ( 1<= a_i <= 1000 )

Output

output contains only one integer the maximum amount of sugar they can get.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1. C language is the only allowed programming language. Solving problems with other languages (e.g. C++) 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:

   • 11617: 7 points

   • 12137: 5 points

   • 12138: 5 points

   • 12139: 9 points

   • 12134: 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