Էմիլը և հակառակորդները
Էմիլը նվեր էր ստացել 1-ից n թվերի ինչ-որ տեղափոխություն։ Բայց Էմիլը ուներ բազմաթիվ հակառակորդներ, որոնք նենգաբար գողացան Էմիլի նվերը։
Քանի որ Էմիլը ավելի խելացի էր քան իր հակառակորդները ու գիտեր սպասվող վտանգի մասին, նախօրոք գրի էր առել տեղափոխության համարներով տարրերի արժեքները։
Դրանից բացի Էմիլը հիշում էր, որ տեղափոխությունը կարելի էր տրոհել այնպիսի հաջորդական հատվածների, որ ամեն տարր կպատկաներ ճիշտ մեկ հատվածի ու տրոհմանը պատկանող կամայական հատվածի երկարությունը (որը հավասար է r-l+1) առանց մնացորդի կբաժանվեր կամ -ի վրա, կամ -ի վրա։
Քանի որ Էմիլը բավականին զբաղված մարդ է, օգնեք նրան վերականգնել հաջորդականությունը։
Երաշխավորվում է, որ գույություն ունի Էմիլի նշումներին համապատասխանող տեղափոխություն։ Եթե գոյություն ունեն Էմիլի նշումներին համապատասխանող մեկից ավելի տեղափոխություններ, ապա կարելի է վերականգնել դրանցից կամայականը։
Մուտքային տվյալներ
Առաջին տողում տրված են
n և k թվերը (1 ≤ n ≤ , 0 ≤ k ≤ n)։Հաջորդ k տողերից յուրաքանչյուրում տրված են և թվերը։
Ելքային տվյալներ
Ելքի առաջին տողում պետք է արտածել n թվեր՝ տեղափոխությունը։
Օրինակ
Մուտք | Ելք |
1 0 | 1 |
5 3
1 4
4 5
5 2 | 4 1 3 5 2 |
10 5
1 3
4 2
5 4
9 1
10 8 | 3 5 6 2 4 7 9 10 1 8 |
Օրինակի բացատրություն
3-րդ օրինակում 3 5 6 2 4 7 9 10 1 8 տեղափոխությունը կարելի է տրոհել հաջորդական հատվածների հետևյալ կերպ՝ [3 5 6 2] [4 7 9 10] [1 8]. առաջին հատվածի երկարությունը կբաժանվի 2-ի, երկրորդինը` 4-ի, իսկ երրորդինը` 1-ի:
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները
- Ենթախնդիր 1 (5 միավոր)
1 ≤ n ≤, k = 0
- Ենթախնդիր 2 (5 միավոր)
1 ≤ n ≤, k = 1
- Ենթախնդիր 3 (10 միավոր)
2 ≤ n ≤, k = 2
- Ենթախնդիր 4 (10 միավոր)
1 ≤ n ≤ 10, k ≤ n
- Ենթախնդիր 5 (10 միավոր)
10 ≤ n ≤ 1000, n-5 ≤ k ≤ n
- Ենթախնդիր 6 (15 միավոր)
10 ≤ n ≤, n-5 ≤ k ≤ n
- Ենթախնդիր 7 (20 միավոր)
1 ≤ n ≤, k ≤ n/10
- Ենթախնդիր 8 (25 միավոր)
1 ≤ n ≤, k ≤ n/2
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB