Tý cần giải bài toán sau:

Nam đang chơi trò xếp các số có chữ số tăng dần. Một số được gọi là tăng dần nếu các chữ số của nó từ trái sang phải tăng dần (không kể các chữ số \(0\) vô nghĩa ở đầu). Ví dụ: \(123\), \(48\), \(7\) là số tăng dần; \(122\), \(321\) không phải.

Cho \(L, R, K\), hãy tìm số thứ \(K\) trong đoạn \([L, R]\) khi sắp xếp các số tăng dần theo thứ tự từ bé đến lớn.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Input

• Một dòng duy nhất chứa ba số nguyên \(L, R, K\) (\(0 \le L \le R \le 10^{18}\), \(1 \le K \le 10^{18}\)).

Output

• Số thứ \(K\) thỏa mãn, hoặc \(-1\) nếu có ít hơn \(K\) số thỏa mãn.

Ví dụ

Ví dụ 1

Input:
1 50 5
Output:
13

Giải thích: Các số tăng dần trong \([1, 50]\) là \(1,2,3,4,5,6,7,8,9,12,13,14,15,16,17,18,19,23,24,25,26,27,28,29,34,35,36,37,38,39,45,46,47,48,49\). Số thứ 5 là \(13\).

Ví dụ 2

Input:
100 200 100
Output:
-1

Subtask