Արսենը և խոզուկները
Արսենը նվեր է ստացել
n x n չափի վանդակավոր դաշտ, որի (1, 1) կոորդինատներով վանդակում տեղադրել է k խոզուկների։ Ամեն վանդակ կարող է ունենալ որոշակի բարձրություն, ու քանի որ Արսենի խոզուկները ցատկել չգիտեն՝ կարող են ընթացիկ վանդակից տեղափոխվել դեպի հարևան վանդակ (վերև, ներքև, աջ, ձախ) միայն այն դեպքում, երբ հարևան վանդակի բարձրությունը ավելի փոքր է քան ընթացիկ վանդակի բարձրությունը։Արսենը նաև
m հատ վանդակների վրա տեղադրել է գազարներով լի արկղեր այնպես, որ ոչ մի երկու արկղ չեն գտնվում նույն տողի կամ նույն սյան վրա, ինչպես նաև ոչ մի արկղ չի գտնվում առաջին կամ վերջին տողի կամ սյան վրա։Հիմա Արսենը ուզում է ընտրել վանդակների բարձրություններն այնպես, որ բոլոր բարձրությունները լինեն իրարից տարբեր դրական ամբողջ թվեր ու գոյություն ունենան ճիշտ
k տարբեր ճանապարհներ, որոնք անցնում են բոլոր գազարի արկղեր պարունակող վանդակներով ու վերջանում են (n, n) վանդակում (գազարի արկղերով վանդակները այցելելու հերթականությունը Արսենի ու խոզուկների համար կարևոր չէ)։Օգնեք նրան որոշել վանդակների բարձրությունները։ Եթե գոյություն ունեն մեկից ավելի լուծումներ, ապա կարելի է արտածել դրանցից ցանկացածը։
Մուտքային տվյալներ
Առաջին տողում տրված են
n, m և k թվերը (2 ≤ n ≤ 1000, 0 ≤ m ≤ n - 2, 1 ≤ k ≤ 109)։Հաջորդ
m տողերից յուրաքանչյուրում տրված են գազարով արկղերի կոորդինատները՝ r_i և c_i թվերը (1 < r_i, c_i < n)։Ելքային տվյալներ
Ելքի
n տողերում պետք է արտածել իրարից բացատով անջատված n թվեր, որոնք ներկայացնում են համապատասխան վանդակների բարձրությունները:Օրինակ
Մուտք | Ելք |
5 1 2
2 3 | 12 11 10 14 15
16 23 9 24 25
17 22 8 6 5
18 21 7 13 4
19 20 3 2 1 |
7 3 1
2 3
5 4
4 6 | 17 16 18 19 20 21 2223 15 14 13 12 11 2425 26 27 28 29 10 3031 32 33 7 8 9 3435 36 37 6 38 39 4041 42 43 5 44 45 4647 48 49 4 3 2 1 |
Օրինակի բացատրություն
Առաջին օրինակում երկու ճանապարհները ունեն հետևյալ տեսքը՝
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները
- Ենթախնդիր 1 (5 միավոր)
n ≤ 100, k = 1
- Ենթախնդիր 2 (10 միավոր)
n ≤ 100, k = 2
- Ենթախնդիր 3 (10 միավոր)
n ≤ 100, m = 0, k ≤ n/2
- Ենթախնդիր 4 (10 միավոր)
n = 100, m = 0, k ≤ 1000
- Ենթախնդիր 5 (10 միավոր)
n = 100, m = 0, k ≤ 109
- Ենթախնդիր 6 (20 միավոր)
n = 1000, m ≤ 3, k ≤ 109
- Ենթախնդիր 7 (35 միավոր)
n = 1000, m ≤ 13, k ≤ 109
Constraints
Time limit: 0.5 seconds
Memory limit: 1000 MB
Output limit: 10 MB