A. Эртний Троллууд IV

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

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

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

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

Вася "The Elder Trolls IV" тоглоомоор тоглож байлаа. Ээ дээ энэ компьютер тоглоомын зохиогчид уу! Тэд юуг ч бодож олж чадахаар улс шүү. Энэ тоглоом үнэхээр онцгой мангасуудтай болжээ. Тэдгээрийн нэг нь "Дийлдэшгүй Нударга" нэрт мангас юм. Яагаад түүнийг "дийлдэшгүй" гэж нэрлэсэн бэ гэж үү?

Яагаад гэвэл нэгдүгээрт түүнийг зөвхөн зүсэж л гэмтээх боломжтой. Тиймээс хоёр гардан далайж барьдаг зэвтэй лантуунд дурлагчдад гэж л хэлэхэд "Дийлдэшгүй Нударга"-д зориулагдсан хутганы эрэлд гарахаас өөр аргагүй юм. Хоёрдугаарт "Дийлдэшгүй Нударга"-д зориулсан хутгыг маш олноор нь бэлтгэх хэрэгтэй юм. Маш олныг! Тийм ээ наад бодож байгаагаас чинь ч олныг!

Вася өөрийнхөө баатрыг аль хэдийн $80$-р үе хүртэл хөгжүүлсэн ба хэрэв "Дийлдэшгүй Нударга"-г ялвал $81$-р үед орно. Энэ мангас маш сонин хэлбэртэй. Тэгш өнцөгт паралелопипед шиг харагдах бөгөөд $x × y × z$ хэмжээтэй. Энэ мангас хуваагдашгүй $1 × 1 × 1$ хэмжээтэй шоонуудаас тогтоно. Нэг зүсэлтээр Вася мангасыг зураасны дагуу хувааж чадна. Өөрөөр хэлбэл зүсэлт нь паралелопипедийн аль нэг талтай паралель байх ёстой. Хуваагдсан хэсгүүдийн тоо тодорхой шидэт тоог давбал мангас үхнэ.

Мангасыг цавчих үед хуваагдсан хэсгүүд салж унахгүйгээр байрандаа байсаар байна. Тэгэхлээр Вася нэг цавчилтаар хэд хэдэн хэсгүүдийг зэрэг хувааж чадна гэсэн үг.

Вася $k$ цавчилтын дараа мангасыг хамгийн ихдээ хэдэн хэсэг болгон хувааж чадахаа мэдэхийг хүсэж байна. Түүнд тусална уу. Аан тийм, Васягийн баатар нь хязгаартай урттай, үнэмлэхүй нимгэн сэлмээр цавчдаг юм.

Оролт

Эхний мөр нь $x, y, z, k$ тоонуудаас бүтнэ. ($1 ≤ x, y, z ≤ 10^{6}, 0 ≤ k ≤ 10^{9}$).

Гаралт

Бодлогын хариу болох ганц тоо байна.

C++ 64 бит бүхэл тоог унших үедээ %lld ашиглахгүй байна уу. %64d юм уу cout ашиглана уу.

Орчуулсан: gmunkhbaatarmn

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

Оролт
2 2 2 3
Гаралт
8
Оролт
2 2 2 1
Гаралт
2

Тэмдэглэл

Эхний жишээнд Вася хоорондоо перпендикуляр байх $3$ цавчилт хийнэ. Эхний цавчилтаар мангасыг $2$ хуваах ба хоёр дахь цавчилтаар хуваагдсан хэсэг бүрийг ахин хоёр хэсэг болгон хуваана. Эцэст нь хуваагдсан $4$ хэсэг бүрээ дахин хоёр хэсэг болгон хуваана.

Сэтгэгдлүүдийг ачааллаж байна...