Masala D

Asilbek o‘zining tomorqasida juda g‘alati o‘yin taxtasini topdi. Ajablanarlisi shundaki, bu taxta \(R \times C\) o‘lchamdagi kvadrat kataklardan iborat ekan.
Qatorlar yuqoridan pastga \(0\) dan \(R−1\) gacha, ustunlar esa chapdan o‘ngga \(0\) dan \(C−1\) gacha raqamlangan.

Bu taxtani g‘alati qiladigan jihat — bu kataklarning bo‘yalish tartibi. Har bir katak quyidagi qoidalarga ko‘ra oq yoki kulrang bo‘yalgan:

• Agar qator raqamini \(x\) va ustun raqamini \(y\) deb olsak, \(x \ \& \ y ≥ 1\) bo'lsa, ushbu katak oq rangga bo'yalgan. Bu yerda \(\&\) - bitwise and operatori.
  Masalan, \((4,5)\) katagi — oq rangda bo‘ladi.
• Aks holda katak kulrang bo‘ladi.
  Masalan, \((2,5)\) katagi — kulrang rangda bo‘ladi.

Quyidagi rasmda \(10 \times 10\) o‘lchamdagi taxta ko‘rsatilgan.

Asilbekning tipratikani ushbu g‘alati taxtada yurishni juda yoqtiradi va yurish uslubi ham noodatiy.

Tipratikan o‘z yurishini \((0,0)\) katakdan boshlaydi va yuqoridagi rasmda ko‘rsatilgandek zig-zag tartibda harakat qiladi.

Tipratikan harakatlanayotganda Asilbek, tipratikan bosib o‘tgan kulrang kataklar sonini sanaydi.

Tipratikan \(K\) ta katakdan o‘tganidan so‘ng charchaydi va uxlab qoladi. Asilbek ham, kulrang kataklar sonini hisoblashga ulgurganidan hursand bo‘lib, uxlashga yotadi.

Sizning vazifangiz — taxta o‘lchami va \(K\) qiymati ma’lum bo‘lsa, tipratikan o‘tgan kulrang kataklar sonini hisoblab beruvchi dastur tuzish.

Birinchi qatorda ikkita butun son \(R\) va \(C\) \((1 \leq R, C \leq 1\,000\,000)\)— taxtaning o‘lchamlari beriladi.

Ikkinchi qatorda bitta butun son \(K\) \((1 \leq K \leq R \times C)\) — tipratikan bosib o‘tgan kataklar soni beriladi.

Bitta butun son chiqaring — tipratikan bosib o‘tgan kulrang kataklar soni.