На Жучко му здодеало да бојадисува куќи, па одлучил повторно да го запише неговиот омилен факултет по информатички науки. Елим, познатиот професор на факултетот, решил да му докаже на Жучко зошто бојадисувањето е посоодветна работа за него. Тој му дал на Жучко низа А од N броеви.

Потоа тој му поставил Q прашанки поврзани со дадената низа.

Сите прашанки на професорот имале иста форма и биле претставени преку три цели броеви L, R и X, кои го означувале следното прашање: Колку најмалку пати е потребно да се зголеми или намали бројот X за 1, со тоа што новодобиениот број ќе биде прост број и ќе дели барем еден од броевите кои се наоѓаат во низата А од нејзината L-та позиција до нејзината R-та позиција?

Откако ја чул задачата, Жучко веднаш, со голема самодоверба, се вратил на бојадисување. Доколку одлучите да се запишувате на овој престижен факултет, потребно е да напишете програма која ќе ги одговори сите Q прашанки.

Влез

Во првиот ред се дадени два цели броја N и Q (1 ≤ N ≤ 1 000 000 и 1 ≤ Q ≤ 100 000) - бројот на елементи во низата A и бројот на прашанки кои Елим му ги поставил на Жучко.

Во следниот ред се дадени N цели броеви - елементите на низата A, каде за секој елемент A_i важи: 2 ≤ A_i ≤ 1 000 000.

Во наредните Q редови дадени се по три цели броеви: L_i, R_i, X_i (1 ≤ L_i ≤ R_i ≤ N и 1 ≤ X_i ≤ 1 000 000), кои ја опишуваат i-тата прашанка.

Забелешка.
За 30% од поените важи: N, Q ≤ 1 000.
За дополнителни 20% од поените важи: N, Q ≤ 20 000.
За дополнителни 30% од поените важи: N ≤ 200 000.

Излез

Отпечатете Q редови, секој со по еден цел број - одговорот на соодветната прашанка.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 128 megabytes

Примери

влез
6 3
2 7 6 10 4 21
1 3 8
2 4 4 
4 6 10

излез
1
1
3

Објаснување за примерот:

Во првата прашанка може бројот X еднаш да го намалиме за еден, со што ќе го добиеме бројот 7, кој е прост број и воедно го дели вториот елемент во низата A. За втората прашанка, може X да го зголемиме за 1, со што ќе го добиеме бројот 5, кој е прост и воедно го дели 4-тиот број во низата A. За третата прашанка, потребно е бројот X да го намалиме три пати, со што ќе го добиеме бројот 7, кој е прост и воедно го дели шестиот број во низата A.