F. Поликарп ба өвс

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

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

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

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

Фермер Поликарп өвстэй агуулахтай ба энэ нь $n × m$ тэгш өнцөгт хүснэгтээр дүрслэгдэж болох бөгөөд энд $n$ нь хүснэгтийн мөрийн тоо ба $m$ нь хүснэгтийн баганын тоо байна. Хүснэгтийн нүд бүр нь нуруу өвс агуулна. $i$-дахь мөр болон $j$-дэх баганад байрлалтай өвсний өндөр нь бүхэл тоон $a_{i, j}$ метртэй тэнцүү ба нуруу өвсөн доторх куб метр өвсний тоотой давхацна, учир нь бүх нүд нь $1 × 1$ хэмжээтэй суурьтай байна. Поликарп бухал бүрийн дээрээс дурын хэмжээний бүхэл тоон куб метр өвс авч хаях замаар агуулахаа цэгцлэхээр шийджээ. Та ялгаатай нуруу өвснөөс ялгаатай хэмжээний өвс авч болно. Түүнээс гадна, бухалд огт хүрэхгүй байх, эсвэл, эсрэгээрээ, бухлыг бүр мөсөн авч хаях нь зөвшөөрөгдсөн. Хэрэв бухал бүр мөсөн авч хаягдсан бол, харгалзах нүд нь хоосон болох ба дахин бухал агуулахгүй юм.

Поликарп шинэчлэлийн дараа дараах шаардлагуудыг хангахыг хүсэж байгаа:

  • агуулахад үлдсэн нийт өвсний хэмжээ заавал $k$-тай тэнцүү байна,
  • бүх бухлуудын (өөрөөр хэлбэл, 0-ээс ялгаатай хэмжээний өвс агуулж буй нүднүүд) өндөр заавал ижил байна,
  • дор хаяж нэг бухлын өндөр ямар байснаараа үлдсэн байх ёстой,
  • үлдсэн бүтцийн тогтвортой байдалд зориулж бүх бухлууд нь нэг холбогдсон бүс нутаг хэлбэртэй байх ёстой.

Хэрэв 2 бухал нь хүснэгт доторх талаараа нийлж байвал тэдгээрийн зэргэлдээ гэж үзнэ. Хэрэв тухайн бүс нутгийн ямар ч бухлаас та уг бүс нутгийн ямар ч бусад бухал уруу зөвхөн зэргэлдээ бухал уруу нүүх замаар очиж болж байвал уг бүс нутгийг холбогдсон гэж нэрлэнэ. Энэ тохиолдолд 2 зэргэлдээ бухал нь ижил бүс нутагт харьяалагдах шаардлагатай.

Поликарп-д уг өрсөлдөөнт даалгаврыг биелүүлж эсвэл энэ нь боломжгүй талаар мэдэгдэнэ үү.

Оролт

Эхний мөрөнд 3 бүхэл тоо $n$, $m$ ($1 ≤ n, m ≤ 1000$) болон $k$ ($1 ≤ k ≤ 10^{18}$) өгөгдөнө -- эдгээр нь овоолсон өвс байрлах тэгш өнцөгт хүснэгтийн мөрийн тоо болон баганын тоо мөн шинэчлэлийн дараах шаардлагатай өвсний нийт куб метрийн тоог илэрхийлнэ.

Дараа нь $n$ мөр өгөгдөх ба, тус бүр нь $m$ ширхэг эерэг бүхэл тоо $a_{i, j}$ ($1 ≤ a_{i, j} ≤ 10^{9}$)-уудыг агуулна, энд $a_{i, j}$ нь хүснэгтийн $i$-дахь мөр болон $j$-дэх баганын өвсөн бухлыг үүсгэх куб метр өвсний тоотой тэнцүү байна.

Гаралт

Эхний мөрөнд хэрэв Поликарп шинэчлэлийг хийж чадах бол "YES" (хашилтгүйгээр) гэж хэвлэнэ үү, бусад тохиолдолд "NO" (хашилтгүйгээр) гэж хэвлэнэ үү. Хэрэв хариулт нь "YES" (хашилтгүйгээр) байвал, дараагийн $n$ мөрөнд $m$ тоонуудыг хэвлэнэ -- эдгээр нь үлдсэн өвсөн бухлуудын өндрийг илэрхийлнэ. 0-ээс ялгаатай бүх үлдсэн утгууд нь тэнцүү байх ёстой ба эдгээр нь холбогдсон бүс нутгийг дүрслэх бөгөөд эдгээрийн дор хаяж нэг утга нь өөрчлөгдөөгүй байх ёстой.

Хэрэв олон тооны хариулт байвал, алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

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

Оролт
2 3 35
10 4 9
9 9 7
Гаралт
YES
7 0 7 
7 7 7 
Оролт
4 4 50
5 9 1 1
5 1 1 5
5 1 5 5
5 5 7 1
Гаралт
YES
5 5 0 0 
5 0 0 5 
5 0 5 5 
5 5 5 0 
Оролт
2 4 12
1 1 3 1
1 6 2 4
Гаралт
NO

Тэмдэглэл

Эхний жишээнд 0-ээс ялгаатай утгууд нь холбогдсон бүх нутаг үүсгэх ба тэдгээрийн утгууд нь өвсөн бухлуудын анхны өндрөөс хэтрэхгүй байна. Бүх 0-ээс ялгаатай утгууд нь $7$-той тэнцүү ба тэдгээрийн тоо нь $5$, иймд үлдсэн өвсний нийт эзлэхүүн нь шаардлагатай утгатай тэнцүү байна $k = 7*5 = 35$. 2-дахь эгнээний 3-дахь байрлалд байх бухал нь өөрчлөгдөөгүй хэвээр байна.

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