Word Counting

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 256M

Problem type

One of Oliver's chores is organizing his bookshelf. In order to do so, he needs to know how many words are in each of his Q books. Oliver's friend, Colin, has a massive brain, so he knows that the i-th (1 \le i \le Q) book contains w_{i} words. Unfortunately, Colin is a troll and decides not to tell Oliver the number of words in the books.

Instead, Colin got his hands on N magic buttons. The i-th of these buttons (1 \le i \le N) converts a book into p_{i} pages, with an equal number of words on each page (note that the number of words on the page does not need to be an integer). Colin will use one of the N magic buttons on each of the Q books (note that the same button can be used on multiple different books). Once Colin has done this, Oliver will figure out the number of words in each book. Oliver does this by counting the number of words on the first page, then counting the number of pages in the book and multiplying the two numbers together. Oliver takes one unit of time to count each word and one unit of time to count each page.

Because Colin isn't that big of a troll, he decides to use the buttons that minimize the amount of time Oliver will spend counting. Can you tell Colin what button he should use for each book?

Input Specification

The first line will contain two integers N (1 \le N \le 10^{5}) and Q (1 \le N \le 10^{5}).

The next line will contain N integers. The i-th integer will be p_{i} (1 \le p_{i} \le 10^{9}).

The next line will contain Q integers. The i-th integer will be w_{i} (1 \le w_{i} \le 10^{9}).

Output Specification

Print Q space separated integers. The i-th (1 \le i \le Q) of these integers should contain the index of the button that Colin should use for the i-th book to minimize Oliver's counting time. If there are multiple indices that minimize the time, print the smallest one.

Sample Input

5 4
2 4 5 1 8
8 1 20 1000000000

Sample Output

1 4 2 5

Sample Explanation

The first and second buttons both result in the minimum counting time for the first book, but the button with index one is used because it has the smaller index of the two. When button one is used, the number of pages is 2 and the number of words per page is 8 / 2 = 4, resulting in a counting time of 4 + 2 = 6.


There are no comments at the moment.