E. Гурван морь

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Морины ертөнцөд саарал, цагаан, цагаан саарал гурван морь амьдардаг. Эдгээр морьд үнэхээр инээдтэй амьтад, учир нь тэд онцгой картуудыг шүтдэг. Эдгээр карт бүр хоёр бүхэл тоо агуулсан байх ёстой ба эхний тоо картны дээр, хоёр дахь тоо картны доор байна. Картны дээр нь $a$ тоо, доор нь $b$ тоо байдаг гэдгийг $(a, b)$ гэж илэрхийлье.

Эдгээр гурван морь гурвуулаа онцгой карт зурж чаддаг. Хэрвээ та саарал моринд $(a, b)$ карт харуулвал тэр $(a + 1, b + 1)$ байх шинэ карт зурж чаддаг. Харин цагаан моринд $a$ ба $b$ нь тэгш байх $(a, b)$ карт харуулвал тэр $(a/2, b/2)$ байх шинэ карт зурж чаддаг. Мөн та цагаан саарал моринд $(a, b)$ ба $(b, c)$ картууд харуулвал тэр $(a, c)$ байх шинэ карт зурж чаддаг.

Поликарпус $n$ ширхэг $(1, a_{1})$, $(1, a_{2})$, $...$, $(1, a_{n})$ онцгой картууд авахыг үнэхээр их хүсдэг. Үүний тулд тэр морины ертөнц рүү явжээ. Энд тэр $1 ≤ x < y ≤ m$ байх $(x, y)$ карт авч чадна. Мөн тэр энэ газар зарим нэг үйлдлүүдийг гүйцэтгээд өөрийн хүссэн картаа авахын тулд карт сонгох хэдэн арга байгаа вэ?

Поликарпус морьдоос зөвхөн дээр дурдсан үйлдлүүдийн үр дүнд үүсэх картуудыг авч чадна. Мөн Поликарпус өөрийн хүссэн картаасаа гадна нэмэлт карт авах боломжтой юм.

Оролт

Эхний мөр нь $n, m$ $(1 ≤ n ≤ 10^{5}, 2 ≤ m ≤ 10^{9})$ хоёр бүхэл тоог агуулна. Хоёр дахь мөр нь $a_{1}, a_{2}, ..., a_{n}$ $(2 ≤ a_{i} ≤ 10^{9})$ бүхэл тоонуудын дарааллыг агуулна. Дарааллын тоонууд давхцаж болно гэдгийг анхаараарай.

Гаралт

Асуултын хариулт болох нэг бүхэл тоо хэвлэнэ.

С++ хэлний оролт гаралтын хэлбэрт $\%lld$ буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл $\%I64d$ хэлбэрийг ашиглавал тохиромжтой..

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
1 6
2
Гаралт
11
Оролт
1 6
7
Гаралт
14
Оролт
2 10
13 7
Гаралт
36
Сэтгэгдлүүдийг ачааллаж байна...