Hôm nay là \(1\) ngày đẹp trời, Shiba quyết định đi siêu thị mua bơ. Có \(N\) hộp bơ ở siêu thị hiện giờ, đạp vô mắt Shiba bây giờ toàn là các bảng, mác tiền của các loại bơ, loại bơ thứ \(i\) có giá thành là \(a_i\). Hiện máy thanh toán của siêu thị đang bị lỗi, với mỗi sản phẩm mà chia lấy dư cho \(k\) bằng \(0\) thì máy sẽ thanh toán sản phẩm đấy với giá là \(0\), tiền của Shiba đã hết nên đã dùng sơ hở này để mua bơ, anh ta chỉ mua bơ với giá đúng bằng \(0\), tức là giá hộp bơ đó phải được thanh toán là \(0\).

Shiba có \(Q\) câu hỏi để sở hữu các hộp bơ từ \(l\) đến \(r\), với \(k\) là lỗi của máy thanh toán, Shiba cần thực hiện bao nhiêu thao tác sau đây. Trong \(1\) thao tác có thể thực hiện chọn \(1\) đoạn bất kì rồi cộng đoạn đó lên \(1\) đơn vị hoặc trừ đi \(1\) đơn vị. Hãy tính số thao tác tối thiểu cần thực hiện.

Input

• Dòng đầu tiền gồm số \(2\) số nguyên dương \(N\), \(Q\) \(-\) \(N\) là số hộp bơ trong siêu thị, \(Q\) là số câu hỏi của Shiba.

• Dòng tiếp theo gồm \(N\) số nguyên không âm \(a_i\) là giá của hộp bơ thứ \(i\).

• \(Q\) dòng còn lại, mỗi dòng gồm \(3\) số nguyên dương \(l\),\(r\),\(k\). Yêu cầu để sở hữu hộp bơ từ \(l\) đến \(r\) với lỗi của máy thanh toán là \(k\) thì số thao tác tối thiếu là bao nhiêu để sau khi thực hiện xong với mỗi giá của hộp bơ trong đoạn \(l\) đến \(r\) chia lấy dư cho \(k\) bằng \(0\).

Dữ Liệu Vào đảm bảo \(k\) luôn luôn lớn hơn giá tiền của các hộp bơ và giá tiền mỗi hộp bơ là không âm.

Output

• In ra Màn hình gồm \(Q\) dòng, dòng thứ \(i\) là số thao tác tối thiểu cho câu hỏi thứ \(i\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(N \le 10\), \(Q = 1\), \(k \le 10\);
• Subtask \(2\) (\(20\%\) số điểm): Có \(N \le 10^3\), \(Q = 1\), \(k \le 2^{30}\);
• Subtask \(3\) (\(20\%\) số điểm): Có \(N \le 2 \times 10^5\), \(Q = 1\), \(k \le 2^{30}\);
• Subtask \(4\) (\(10\%\) số điểm): Có \(N \le 2 \times 10^5\), \(1 \le Q \le 10^5\), \(k \le 2\);
• Subtask \(5\) (\(20\%\) số điểm): Có \(N \le 3 \times 10^4\), \(1 \le Q \le 3 \times 10^4\), \(k \le 2^{30}\);
• Subtask \(6\) (\(20\%\) số điểm): Có \(N \le 2 \times 10^5\), \(1 \le Q \le 10^5\), \(k \le 2^{30}\).

Example

7 4
4 5 6 4 5 6 7
4 5 8
3 7 10
2 5 17
1 7 12

4
6
7
9