시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 256 MB | 21 | 11 | 11 | 84.615% |
Lately, Slavko’s been studying sequences of natural numbers. He finds a sequence interesting if the greatest common divisor of all the elements from the sequence is greater than 1.
Yesterday, he found a sequence consisting of N natural numbers in his garage. Since he was really bored, he decided to keep himself occupied by asking simple queries. Each query can be one of the two types:
The first line of input contains the numbers N and Q (1 ≤ N, Q ≤ 105), representing the number of elements in the sequence and the number of queries, respectively.
The following line contains N natural numbers Ai (1 ≤ Ai ≤ 109) that represent the numbers in the initial sequence.
Each of the following Q lines contains a query of the following form:
For each query of type 2, output the number of interesting contiguous subarrays from the task.
5 1 8 4 3 9 1 2 2 5
4
5 3 2 3 6 4 1 2 1 4 1 3 1 2 3 5
6 1
4 3 2 2 2 2 2 1 4 1 2 3 2 1 4
10 5
Clarification of the first test case: The interval from the 2 nd to the 5 th position consists of numbers (4, 3, 9, 1). In it, the following are interesting contiguous subarrays (denoted with square brackets): [4] 3 9 1, 4 [3] 9 1, 4 3 [9] 1, 4 [3 9] 1