Васяа-ийн төрсөн өдөр болох гэж байгаа ба түүний ээж түүнд $n$ урттай эерэг бүхэл $a$ массив өгөхөөр шийдсэн.

Васяа хамгийн их ерөнхий хуваагчтай массивийг гоё массив гэж бодсон. Түүний ээж мэдээж хэрэг түүнд аль болох гоё массив өгөхыг хүссэн. Харамсалтай нь дэлгүүрт зөвхөн $a$ массив л үлдсэн байсан. Худалдагч нь массивийн зарим элементийг бууруулж болно гэж хэлсэн ($k$-аас ихээр буруулж болохгүй).

Худалдагч $a$ матрицаас $b$ матрицийг олж авхад дараах дүрмийг дагаж авах боломжтой. Үүнд: $b_{i} > 0; 0 ≤ a_{i} - b_{i} ≤ k$; $1 ≤ i ≤ n$.

Васяа-аад өгөх гоё массивд хамгийн боломжтой массивийг олоход нь түүний ээжид туслаарай.

Оролт

Эхнй мөрөнд хоёр бүхэл $n$ ба $k$ $(1 ≤ n ≤ 3*10^{5}; 1 ≤ k ≤ 10^{6})$ тоонууд оруулна. Хоёр дахь мөрөнд $n$ ширхэг $a$ массивийн $a_{i}$ $(1 ≤ a_{i} ≤ 10^{6})$ элементүүдийг оруулна.

Гаралт

Ганц мөрөнд нэг тоо хэвлэнэ. Энэ тоо нь гоё массивийн хамгийн их ерөнхий хуваагч юм.

Эхний жишээнд бид энэ массивийг авч чадна:

$3 6 9 12 12 15$

Хоёр дахь жишээнд бид энэ дараагийн массивийг авна:

$7 21 49 14 77$