В твоих руках массив 
a
a из 
n
n целых чисел.

Назовем подотрезок этого массива 
[
ℓ
,
r
]
[ℓ,r] 
k
k-интересным 
(
k
≥
1
)
(k≥1), если существует такое целое число 
m
≥
k
m≥k, что 
a
ℓ
m
o
d
 
 
m
=
a
ℓ
+
1
m
o
d
 
 
m
=
a
ℓ
+
2
m
o
d
 
 
m
=
.
.
.
=
a
r
m
o
d
 
 
m
a 
ℓ
​
 modm=a 
ℓ+1
​
 modm=a 
ℓ+2
​
 modm=...=a 
r
​
 modm. Здесь 
m
o
d
mod обозначает операцию взятия остатка от деления. То есть все элементы на этом подотрезке равны по модулю 
m
m.

Тебе предстоит ответить на 
q
q запросов.

Каждый запрос — тройка 
(
ℓ
,
r
,
k
)
(ℓ,r,k). В ответ на запрос посчитайте количество 
k
k-интересных подотрезков массива 
a
[
ℓ
,
r
]
a[ℓ,r]. То есть, найдите количество таких пар 
(
ℓ
1
<
r
1
)
(ℓ 
1
​
 <r 
1
​
 ), что 
ℓ
≤
ℓ
1
<
r
1
≤
r
ℓ≤ℓ 
1
​
 <r 
1
​
 ≤r и подотрезок 
[
ℓ
1
,
r
1
]
[ℓ 
1
​
 ,r 
1
​
 ] является 
k
k-привлекательным.

Будущее этого мира – в твоих руках!

Формат ввода
В первой строке вам даны числа 
1
≤
n
≤
5
⋅
1
0
4
1≤n≤5⋅10 
4
  и 
1
≤
q
≤
1
0
5
1≤q≤10 
5
 , обозначающие число элементов массива и количество запросов. В следующей строке заданы элементы массива — натуральные числа от 
1
1 до 
1
0
9
10 
9
 . В следующих 
q
q строках заданы запросы. Каждая строка содержит тройку 
ℓ
,
r
,
k
ℓ,r,k, где 
1
≤
ℓ
<
r
≤
n
,
1
≤
k
≤
1
0
9
1≤ℓ<r≤n,1≤k≤10 
9
 .

Формат вывода
Для каждого запроса выведи ответ на него в отдельной строке. Все зависит только от тебя!

Примечание
Определения

Подотрезок массива 
a
a 
[
ℓ
,
r
]
[ℓ,r] - набор элементов массива, индексы которых лежат в промежутке от 
ℓ
ℓ до 
r
r, то есть элементы 
(
a
ℓ
,
a
ℓ
+
1
,
…
,
a
r
)
(a 
ℓ
​
 ,a 
ℓ+1
​
 ,…,a 
r
​
 ).

Ограничения
Ограничение времени

3 с

Ограничение памяти

256 МБ

Пример 1
Ввод
5 2
12 6 4 16 8
1 5 4
1 5 2
Вывод
4
10
Пример 2
Ввод
5 10
36 36 81 72 72
1 5 47
1 5 36
1 5 63
1 5 9
1 5 12
1 5 30
1 5 45
1 5 46
1 5 9
1 5 89
Вывод
2
4
2
10
4
4
4
2
10
2
Пример 3
Ввод
10 20
64 64 64 32 80 80 36 90 36 54
6 6 24
2 8 48
2 10 26
8 9 24
4 8 9
5 9 60
2 6 1
6 8 1
8 9 3
5 7 23
5 10 48
5 10 15
3 9 4
1 6 80
6 10 48
2 10 27
4 8 45
2 4 25
2 7 16
2 10 81
Вывод
0
5
11
1
6
1
10
3
1
3
4
9
13
4
3
11
4
3
12
2

Напиши решение на js:


function calculateAnswer(n, a, l, r, k) {
    // your code here
}

// ввод/вывод в самом низу

const fs = require('fs');

class FastInput {
    constructor(filename) {
        this.tokens = fs.readFileSync(filename, 'utf8')
            .trim()
            .split(/\s+/);
        this.index = 0;
    }

    readToken() {
        return this.tokens[this.index++];
    }

    readInt() {
        return parseInt(this.readToken(), 10);
    }

    readLong() {
        return BigInt(this.readToken());
    }

    readTokens(n) {
        const res = this.tokens.slice(this.index, this.index + n);
        this.index += n;
        return res;
    }

    readIntArray(n) {
        const res = new Array(n);

        for (let i = 0; i < n; i++) {
            res[i] = this.readInt();
        }

        return res;
    }
}

// ввод/вывод
// не изменяйте сигнатуру метода
function solution() {
    const inputFile = './input.txt';
    const outputFile = './output.txt';

    const input = new FastInput(inputFile);

    const n = input.readInt();
    const q = input.readInt();

    const a = input.readIntArray(n);

    const results = [];

    for (let i = 0; i < q; i++) {
        const l = input.readInt();
        const r = input.readInt();
        const k = input.readInt();

        const answer = calculateAnswer(n, a, l, r, k);
        results.push(answer);
    }

    fs.writeFileSync(outputFile, results.join(' ') + '\n');
}