题号：NC225186
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
You are given an array of a of size n , 
. We define )
as the minimum number of operations to make 
.
In one operation, first you choose an interval)
, then you can choose either %5Cpmod%20k)
or %5Cpmod%20k)
.
has q queries: given l,r,k , you need to calculate )
.
In one operation, first you choose an interval
输入描述:
The first line cointains n,q , denoting the length of the array a and the number of queries.The second line contains n integers, denoting.
In the next q lines, each line contains l,r,k .
It's guaranteed that, and for every k,
.
输出描述:
For each queries, print