ALIEN0 - Trailing Zeros

There's a line of N numbers where each number is a positive integer that is less than 109. Every second, an alien comes down to the Earth and ask a certain problem. "How many zeros are there after all the other digits when you multiply all the number in range and R ?". Unfortunately, the alien don't know base 10 numbers. In fact, there're 6 species of alien in the UFO, the first species use base-1 number, second use base-2 and so on. (Yes, the first species do not exist, and therefore will not come down to the Earth).

You are given a task to answer the aliens' questions in their numerical system for a day, which mean there're up to 100,000 questions to be answer.

Input

First line, N <= 100000 which is mentioned above and Q <= 100000 representing number of questions.
Next line, N positive integers on the line on earth, each not exceeding 109.
Next Q lines, 1 <= L <= R <= N representing a range each alien mentioned, and 2 <= S <= 6 representing the alien species.

Output

Q lines, each line is a number represent the answer for each alien.

Example

Input:
5 3
2 3 6 5 100
1 5 2
1 3 6
1 2 3  Output: 4
2

Added by:Touch
Date:2020-03-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-05-04 06:56:46 Sushovan Sen
"You are given a task to answer the aliens' questions in their numerical system for a day" a bit confusing, I think answer should be given in decimal system.
"You are given a task to answer the aliens' questions if the numbers in array are represented in their numerical system for a day"
2020-03-28 16:32:48
landi58: This is not an easy problem to approach without some experience. Sort the problem list by number of users and try the most popular ones first. This is more of a general advice, but also my solution here profited from one of these problems I had solved and optimized as a newbie some years ago.

Last edit: 2020-03-28 16:34:39
2020-03-28 15:57:07
My solution is correct by time limit is being exceeded. Please tell me some efficient approach to count number of trailing zeros.
2020-03-10 20:26:14
Nice problem, solvable with Python. Some clarifications:

- "N numbers where each number is a positive integer that is less than 109" -> "array of N positive integers smaller than 10^9"
- "How many zeros are there after all the other digits when you multiply all the number in range L and R ?" -> "How many trailing zeros are in the product of all the numbers in the array between indexes L and R, inclusive, if the product is represented in base S?"
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.