A = [a₁, a₂, ..., aₙ] натурал тоон массив өгөгдөв. A массивын l-ээс r хүртэлх хэрчим гэж [aₗ, aₗ₊₁, ..., aᵣ] массивыг нэрлэе.

Өгөгдсөн A массив ба k тооны хувьд элементүүдийн нийлбэр нь k-д хуваагддаг байх A массивын хэрчмүүдийн тоог ол.

Оролтын формат

Эхний мөрөнд n, k хоёр бүхэл тоо байх ба тэдгээр нь харгалзан A массивын элементийн тоо ба k тоо юм. Хоёр дахь мөрөнд A массивын элементүүд болох [a₁, a₂, ..., aₙ] тоонууд өгөгдөнө.

Гаралтын формат

A массивын l-ээс r хүртэлх хэрчим дээрх элементүүдийн нийлбэр нь k-д үлдэгдэлгүй хуваагддаг байх бөгөөд 1 ≤ l ≤ r нөхцөлийг хангах бүх (l, r) хосын тоог хэвлэнэ.

Хязгаарлалт:

• 1 ≤ n ≤ 200000
• 2 ≤ k ≤ 10⁹
• 1 ≤ aᵢ ≤ 10⁹

Оролт-1

5 2 
1 2 3 4 5

Гаралт-1

6

Тайлбар

Тайлбар: Доорх хүснэгтэд шаардлага хангах хэрчмүүдийн мэдээллийг үзүүлэв: