Два числа являются взаимно простыми, если их наибольший общий делитель равен единице.
Первая строка входного файла INPUT.TXT содержит целое число n – количество чисел (1 ≤ n ≤ 200 000). Во второй строке записаны n целых чисел ai, разделённые пробелами (1 ≤ ai ≤ 106). В третьей строке содержится целое число m – количество запросов (1 ≤ m ≤ 200 000). Следующие m строк содержат тройки чисел li, ri и xi (1 ≤ li ≤ ri ≤ n; 1 ≤ xi ≤ 106).
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6
1 2 3 4 5 6
4
1 6 1
1 6 2
2 4 6
3 6 10 | 6
3
0
1 |
