Skaitmenų seka

시간 제한1초메모리 제한512 MB

요약

숫자열 S를 K+1번 이어 붙인 뒤 자릿수 합 해시를 N번 적용하고, 마지막 자릿수 합의 끝자리를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 구현, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

Irus labai mėgsta skaičių $S$ ir nenori juo dalintis. Kad niekas nesužinotų jo skaičiaus, Irus jį užkoduoja savo patentuotu algoritmu.

Pirmiausiai Irus pailgina skaičių $S$ prie jo pabaigos prijungdamas $K$ jo paties kopijų. Toliau Irus $N$ kartų pritaiko maišos funkciją. Ši funkcija:

Paima turimą (t. y. dalinai užkoduotą) skaičių
Suskaičiuoja šio skaičiaus skaitmenų sumą $d$
Numeta pirmąjį (labiausiai reikšminį) skaitmenį ir prie skaičiaus pabaigos prijungia paskutinįjį skaičiaus $d$ skaitmenį.

Galiausiai Irus paima skaičiaus, gauto $N$ kartų pritaikius maišos funkciją, skaitmenų sumos paskutinįjį skaitmenį, jį įrėmina, ir pasikabina ant sienos.

입력

Pagal duotuosius $S$ , jo ilgį $L\_S$ , $K$ ir $N$ reikia rasti Irus įrėmintą skaitmenį.

출력

Pirmoje eilutėje pateikti sveikieji skaičiai $L\_S$ , $K$ ir $N$ . Antroje eilutėje pateiktas sveikasis skaičius $S$ .

제한

$1 ≤ L\_S ≤ 1\\,000\\,000$
$1 ≤ K ≤ 1\\, 000$
$1 ≤ N ≤ 1\\,000\\,000$
Duomenys tokie, kad kodavimo metu jokio tarpinio skaičiaus pirmojoje pozicijoje neatsiras $0$ .

예제3

예제 1
입력
```
2 2 5
12
```
예상 출력
```
7
```
예제 2
입력
```
1
0 1
```
예상 출력
```
2
```
예제 3
입력
```
2
0 1
2 1
```
예상 출력
```
2
```