okcpp

Despre numărul natural $N$ spunem că are proprietatea okcpp dacă oricum alegem $K$ cifre ale sale vom găsi printre ele cel puţin $P$ cifre distincte (oricare $k$ cel puţin $p$).

Cerinţe

1. Fiind date numerele naturale $K$, $P$, $A$ și $B$ să se calculeze și să se afișeze numărul de numere okcpp din intervalul $[A,B].$
2. Fiind date numerele naturale $K$, $P$ și $N$ să se calculeze și să se afișeze cel mai mic număr okcpp care este mai mare sau egal cu $N.$

Date de intrare

Fişierul de intrare okcpp.in conţine pe primul rând numărul $C$. Dacă $C=1$, atunci pe al doilea rând se vor afla scrise, separate prin spațiu, numerele naturale $K$, $P$, $A$ și $B.$ Dacă $C=2$, atunci pe al doilea rând se vor afla scrise, separate prin spațiu, numerele naturale $K$, $P$ și $N.$

Date de ieșire

Dacă $C=1$, atunci în fişierul de ieşire okcpp.out se va scrie numărul de numere okcpp din intervalul $[A;B].$ Dacă $C=2$, atunci în fişierul de ieşire okcpp.out se va scrie cel mai mic număr natural okcpp care este mai mare sau egal cu $N.$

Restricții și precizări

• $1 \leq P \leq 10$;
• $P \leq K \leq$ numărul de cifre al lui $N \leq 18$;
• Pentru $20\%$ din teste cerinţa va fi $C=1$;
• Pentru cerința $C=1$ vom avea $0 \leq A < B < 10^{18}$ și $B-A \leq 10 \ 000$;
• Pentru cerința $C=2$ se garantează că există întotdeauna soluție.

Exemplul 1

okcpp.in

1
5 2 99997 100001

okcpp.out

3

Explicație

Avem $K=5$ și $P=2$. În intervalul $[99 \ 997; 100 \ 001]$ sunt trei numere $\textbf{okcpp}$: $99 \ 997$, $99 \ 998$ și $100 \ 001.$

Exemplul 2

okcpp.in

2
5 3 99997

okcpp.out

100023

Explicație

Avem $K=5$, $P=3$ şi $N=99 \ 997$. Se observă uşor că numerele $99 \ 997$, $99 \ 998$ , $\dots$, $100 \ 022$ nu corespund. Primul număr care corespunde cerinţelor este $100 \ 023.$