Kristallar va portal siri

Qadimiy minorada \(n\) ta sehrli kristall topilgan, ularning har birida \(a_i\) miqdorda energiya bor. Afsonaga ko'ra, agar ikkita kristallni birlashtirilsa va ularning energiyalari yig'indisi maxfiy son \(k\) ga qoldiqsiz bo'linsa, o'sha juftlik yashirin portalni ochadi.

Sehrgar sizdan yordam so'rayapti: minoradagi barcha kristall juftliklari orasida nechtasi portal ochish qobiliyatiga ega ekanini aniqlab bering — chunki minora qulab tushishidan oldin faqat bitta imkoniyat qoladi, va sehrgar qaysi juftlikni tanlashni oldindan bilmoqchi.

Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi (\(1 \le n \le 2 \times 10^5\); \(1 \le k \le 10^9\)) — kristallar soni va portal sirli soni.

Ikkinchi qatorda \(n\) ta butun son \(a_1, \dots, a_n\) beriladi (\(0 \le a_i \le 10^9\)) — har bir kristallning energiyasi.

Chiquvchi ma'lumotlar

Portal ochishga qodir bo'lgan \((i, j)\) juftliklar sonini chop eting, bunda \(1 \le i < j \le n\) va \((a_i + a_j) \pmod k = 0\).

Misollar

1

4 3
3 1 5 2

2

2

5 5
5 10 15 20 25

10

3

6 4
1 3 2 2 5 7

5

Izoh

1-Test: \(n=4\), \(k=3\), kristallar: \(3, 1, 5, 2\)

Barcha juftliklarni tekshiramiz:

• \(3 + 1 = 4\), \(4 \pmod 3 = 1\) — mos emas
• \(3 + 5 = 8\), \(8 \pmod 3 = 2\) — mos emas
• \(3 + 2 = 5\), \(5 \pmod 3 = 2\) — mos emas
• \(1 + 5 = 6\), \(6 \pmod 3 = 0\) — portal ochiladi \(\checkmark\)
• \(1 + 2 = 3\), \(3 \pmod 3 = 0\) — portal ochiladi \(\checkmark\)
• \(5 + 2 = 7\), \(7 \pmod 3 = 1\) — mos emas

Jami \(2\) ta juftlik portal ochadi: \((1, 5)\) va \((1, 2)\).

2-Test: \(n=5\), \(k=5\), kristallar: \(5, 10, 15, 20, 25\). 

Har bir son \(5\) ga qoldiqsiz bo'linadi (qoldig'i \(0\)), shuning uchun istalgan ikkita kristall birlashsa ham yig'indi \(5\) ga bo'linadi. Jami juftliklar soni \(\binom{5}{2} = \frac{5 \times 4}{2} = 10\).

3-Test: \(n=6\), \(k=4\), kristallar: \(1, 3, 2, 2, 5, 7\).

Har bir kristallni \(4\) ga bo'lgandagi qoldig'iga qarab guruhlaymiz:

• qoldiq \(1\): kristallar \(\{1, 5\}\)
• qoldiq \(3\): kristallar \(\{3, 7\}\)
• qoldiq \(2\): kristallar \(\{2, 2\}\)

Qoldig'i \(2\) bo'lgan guruh o'zi ichida (\(2 + 2 = 4\), \(4 \pmod 4 = 0\)) — \(1\) ta juftlik: \((2, 2)\). Qoldiq \(1\) va qoldiq \(3\) guruhlari o'zaro birlashadi (yig'indi \(4\) karrali bo'ladi): \(1 + 3 = 4\), \(1 + 7 = 8\), \(5 + 3 = 8\), \(5 + 7 = 12\) — \(4\) ta juftlik.

Jami: \(1 + 4 = 5\) ta juftlik portal ochadi.