Description

A famous streamer once said: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA~". This streamer is famous for his "stroke style". If he plays video game with some poor skilled players, he will "stroke". Today he strokes again. He is furious because other players keep "giving head" to his opponents.

---

He gives each player a number b_i denoted as the level of his "stroke". He sorts those numbers in increasing order to make a "stroke list".

Now he gives you t queries. Each query will give you a number a_i, and you should answer the positions of the numbers in the "stroke list".

There will be n numbers in the "stroke list" and all numbers are distinct.

Note that the position starts from 0, and we guarantee that a_i is always on the list.

Hint:

you can use the binary search(https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95) to solve this question.

This question is "partial judge". You only need to complete one function. You should download the two files below and compile those two files and your answer together.

Your submission should only contain your answer.

If you use "codeblocks" or "Xcode" just put all three files(containing your answer) into the same project.

your answer will be like this:

#include "function.h"

int BS(int *陣列名, int 欲尋找的數字, int 陣列長度)
{
	
}

 

⠄⠄⠄⠄⠄⠄⠄
 ⠄⠄⠄⠄⠄⠄⠄⠈⠉⠁⠈⠉⠉⠙⠿⣿⣿⣿⣿⣿
 ⠄⠄⠄⠄⠄⠄⠄⠄⣀⣀⣀⠄⠄⠄⠄⠄⠹⣿⣿⣿
 ⠄⠄⠄⠄⠄⢐⣲⣿⣿⣯⠭⠉⠙⠲⣄⡀⠄⠈⢿⣿
 ⠐⠄⠄⠰⠒⠚⢩⣉⠼⡟⠙⠛⠿⡟⣤⡳⡀⠄⠄⢻
 ⠄⠄⢀⣀⣀⣢⣶⣿⣦⣭⣤⣭⣵⣶⣿⣿⣏⠄⠄⣿
 ⠄⣼⣿⣿⣿⡉⣿⣀⣽⣸⣿⣿⣿⣿⣿⣿⣿⡆⣀⣿
 ⢠⣿⣿⣿⠿⠟⠛⠻⢿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣼
 ⠄⣿⣿⣿⡆⠄⠄⠄⠄⠳⡈⣿⣿⣿⣿⣿⣿⣿⣿⣿
 ⠄⢹⣿⣿⡇⠄⠄⠄⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
 ⠄⠄⢿⣿⣷⣨⣽⣭⢁⣡⣿⣿⠟⣩⣿⣿⣿⠿⠿⠟
 ⠄⠄⠈⡍⠻⣿⣿⣿⣿⠟⠋⢁⣼⠿⠋⠉⠄⠄⠄⠄
 ⠄⠄⠄⠈⠴⢬⣙⣛⡥⠴⠂⠄⠄⠄⠄⠄⠄⠄⠄⠄...
(the photo of the famous streamer)

Input

Input contains several lines.

First line contains two integers n, t (1 <= n, t <= 2*10⁶)

Second line contains n integers b_i ( 1 <= b_i <= 10⁹ )

The following t lines, each line contains one integer a_i ( 1 <= a_i <= 10⁹ )

Output

For each query, you should print the index of the number in this form: "a_i is at index: ans_i ".

Remember to print \n at the end of each query.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12143.c

Partial Judge Header

12143.h

Tags

Discuss

Description

Disclaimer: If something described below happened or happens in real world, which is just a coincidence. We will not take any responsibility of any coincidence.

Uncle: I'm an employee of the library and dating master, nickname "Uncle Huang", who are you?

Shiao: Two years tutor experience, straying book boy of second-hand section, "Shiao Tsing".

Uncle: Well, well. Let me test you!

Uncle: In the painting, dragons won't roar, tigers won't howl, little book boy, funny funny!

Shiao: In the article, man is allowed, woman is forbidden, seeking tutor, urgent urgent!

Uncle: Warbler, swallow, emerald, red, prosperous, harmonious, everywhere.

Shiao: Tutor, Shu-shu, urgent, critial, anxious, serious, swimming pool.

Wang Ye: Another distich!

Uncle: See a jerk standing over there.

Shiao: Seek a tutor swimming over the pool.

Uncle: I am hero in the battle field.

Shiao: You are topic master booming the post.

Uncle: Ahhhhh........!

(Inspired by the post  靠北清大7754)

---

Although uncle Huang loses the distich competition, he is still seeking for a male tutor. He would choose one of those who left comments below his post as his tutor ( and one cannot refuse! ). Because too many people left comments below ( just like Shiao said, he's truly a topic master ), he would pick two numbers "x" and "y", and choose the (x^y)-th person that left a comment as his tutor. 

Because x^y might be too big, so the answer would mod(取模) a number "m", which is the total number of comments of his post.

Uncle Huang is too busy seeking for his true love tutor, he asks you for help, could you help him find out his true love tutor?

---

• You are given three numbers "x", "y", and "m", you have to calculate the answer of ((x^y)%m) .

Hint: Use "Fast Power" method to solve this problem!

Input

The input contains only one line. 

The first line contains exactly three numbers "x", "y", and "m", which are described above. 

1 <= x <= 10¹⁸,, 0 <= y <= 10¹⁸, 1 <= m <= 10⁹.

Output

Output one number: (x^y)%m .

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

Sample Input  Download

Sample Output  Download

Tags

Discuss