{"code":"butter","name":"Mua Bơ","description":"Hôm nay là $1$ ngày đẹp trời, [user: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 [user: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 [user: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$.\r\n\r\n[user: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, [user: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.\r\n\r\n#### Input\r\n- 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 [user:Shiba].\r\n\r\n- 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$.\r\n\r\n- $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$.\r\n\r\nDữ 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.\r\n\r\n#### Output\r\n- 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$.\r\n\r\n#### Scoring\r\n- Subtask $1$ ($10\\%$ số điểm): Có $N \\le 10$, $Q = 1$, $k \\le 10$;\r\n- Subtask $2$ ($20\\%$ số điểm): Có $N \\le 10^3$, $Q = 1$, $k \\le 2^{30}$;\r\n- Subtask $3$ ($20\\%$ số điểm): Có $N \\le 2 \\times 10^5$, $Q = 1$, $k \\le 2^{30}$;\r\n- Subtask $4$ ($10\\%$ số điểm): Có $N \\le 2 \\times 10^5$, $1 \\le Q \\le 10^5$, $k \\le 2$;\r\n- 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}$;\r\n- Subtask $6$ ($20\\%$ số điểm): Có $N \\le 2 \\times 10^5$, $1 \\le Q \\le 10^5$, $k \\le 2^{30}$.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        7 4\r\n        4 5 6 4 5 6 7\r\n        4 5 8\r\n        3 7 10\r\n        2 5 17\r\n        1 7 12\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        6\r\n        7\r\n        9\r\n        ```","points":2300.0,"partial":true,"time_limit":4.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}