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 ≤ P ≤ 10
• P ≤ K ≤ numărul de cifre al lui N ≤ 18
• Pentru 20% din teste cerinţa va fi C=1.
• Pentru cerința C=1 vom avea 0 ≤ A < B < 1018 și B-A ≤ 10000.
• 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=4 și P=2. În intervalul [99997;100001] sunt trei numere okcpp: 99997, 99998 și 100001.

Exemplul 2

okcpp.in

2
5 3 99997

okcpp.out

100023

Explicație

Avem K=5, P=3 și N=99997. Se observă uşor că numerele 99997, 99998, …, 100022 nu corespund. Primul număr care corespunde cerinţelor este 100023.