Cho số nguyên dương không âm ~N~, ở mỗi thao tác bạn thực hiện tính tổng các chữ số của ~N~ sau đó gán lại cho ~N~, thao tác này được thực hiện cho tới khi ~N~ chỉ còn 1 chữ số.

Ví dụ ~N = 9898~ -> ~34~ -> ~7~, vậy ta có dạng rút gọn của ~9898~ là ~7~.

Nhiệm vụ của bạn là tìm dạng rút gọn của 1 số nguyên không âm ~N~ cho trước

Input Format

• 1 dòng chứa số nguyên ~N~ ( ~0 ≤ N ≤ 10^{18} ~ )

Output Format:

• In ra dạng rút gọn của ~N~

Sample Input:

19839823824

Sample output:

3

Giải thích

• ~19839823824~ -> ~57~ -> ~12~ -> ~3~

Trong một thế giới hiện đại với nhiều ga tàu điện ngầm chằng chịt, việc sử dùng tàu điện ngầm giúp con người có thể di chuyển nhanh chóng giữa các vị trí để phục vụ nhu cầu di chuyển bản thân. Bản đồ tàu điện ngầm ở nơi Tùng sống được biểu diễn như sau:

• Mỗi tuyến tàu điện được biểu diễn bằng một danh sách các trạm
• Một số trạm có thể xuất hiện trên nhiều tuyến tàu

Hiện tại Tùng đang cần di chuyển gấp từ điểm A tới điểm B, nhiệm vụ của bạn là phải tìm ra đường tuyến đường tốt nhất cho Tùng sao cho thỏa mãn những điều kiện sau:

• Chỉ đi trên một tuyến đường duy nhất
• Không được đi ngược tuyến đường đã định sẵn
• Số trạm đi qua ít nhất có thể

Ví dụ: Với tuyến đường là 1 2 7, bạn có thể đi từ trạm 1 và dừng ở trạm 2 hoặc trạm 7; hoặc đi từ trạm 2 và dừng ở trạm 7 .Bạn không thể đi ngược lại từ trạm 7 về trạm 1 hay từ trạm 2 về trạm 1.

Input:

• Dòng đầu tiên chứa ba số nguyên ~N~, ~A~ và ~B~, lần lượt là số tuyến đường trong mạng lưới và vị trí của hai điểm dừng cần kết nối. ~(1 ≤ N ≤ 10^4, 1 ≤ A, B ≤ 10^5)~
• ~N~ dòng tiếp theo, mỗi dòng bắt đầu bằng một số nguyên ~k~, là số điểm dừng trong tuyến đường thứ ~i~, theo sau là ~k~ số nguyên biểu diễn mã số của các điểm dừng trên tuyến đó. ~(1 ≤ k ≤ 1000)~

Output:

• Tuyến đường đi tối ưu nhất (qua ít trạm nhất) từ trạm A tới trạm B.
• Nếu không có đường đi thỏa mãn thì in ra -1.

Chia độ khó

Sample input 1:

3 1 7
5 1 2 3 4 7
3 1 5 7 
4 1 4 5 6

Sample output 1:

2

Sample input 2:

4 2 7
3 1 2 4
2 3 9
4 2 5 6 8
3 3 7 9

Sample output 2:

-1

NOTES

• Ở ví dụ 1, có các đường đi từ thành phố 1 tới thành phố 7 như sau:
  • 1 -> 2 -> 3 -> 4 -> 7: tuyến này phải đi qua 4 trạm để tới được chỗ làm
  • 1 -> 5 -> 7: tuyến này phải đi qua 2 trạm để tới được chỗ làm

Đạt vừa mới nhận được công việc làm thêm tại một cửa hàng hoa, hiện nay cửa hàng đã nhập về một số lượng nguyên liệu để chuẩn bị cho đợt 08/03 sắp tới gồm có:

• Số lượng lá: ~m~
• Số lượng hoa: ~n~
• Số lượng giấy gói: ~p~

Lượng nguyên liệu này được dùng để tạo ra các loại bó hoa như sau:

• Bó loại giá ~30.000 đ~: 1 lá, 1 hoa, 3 giấy gói.
• Bó loại giá ~50.000 đ~: 2 lá, 2 hoa, 3 giấy gói.
• Bó loại giá ~70.000 đ~: 3 lá, 5 hoa, 5 giấy gói.

Với giả thiết tất cả loại đều có thể bán hết, hãy tối ưu hóa số lượng mỗi loại bó hoa để thu được tổng số tiền tối đa.

Input:

• Các số nguyên ~m,n,p (1 \leq m,n,p \leq 800)~.

Output:

• In ra tổng số tiền tối đa thu được.

Sample input 1

1 2 5

Sample output 1

30000

Notes

• 1 bó loại 1

Sample input 2

40 26 37 

Sample output 2

600000

Notes

• 12 bó loại 2

Sample input 3

46 60 56 

Sample output 3

920000

Notes

• 17 bó loại 2
• 1 bó loại 3

Hoàng đi rút quẻ đầu năm được thầy bói giao cho một xấp quẻ. Xấp quẻ này khi trải ra được một dãy các cây quẻ, mỗi cây đánh số bất kì từ ~0~ đến ~9~.

Thầy bói yêu cầu Hoàng phải rút đi ~S~ cây quẻ trong xấp. Các quẻ còn lại sẽ được xếp từ trái sang phải, Hoàng tin rằng mình sẽ rất may mắn nếu như dãy quẻ còn lại có giá trị lớn nhất có thể mà không đảo lộn vị trí của các quẻ này.

Với 2 dãy quẻ ~A~ và ~B~ có cùng độ dài, dãy quẻ ~A~ có giá trị lớn hơn dãy quẻ ~B~ nếu như xét cây quẻ có vị trí thứ ~p~ từ trái sang phải, với ~p~ là vị trí đầu tiên mà ~A_i \neq B_i~ thì ~A_i \gt B_i~

Cho dãy quẻ ~X~ và số nguyên ~S~, hãy giúp Hoàng tìm dãy quẻ may mắn của mình.

Input

Dòng đầu tiên chứa dãy quẻ X, dòng thứ hai chứa số S là số cây quẻ cần rút (~1 \leq S \leq N \leq 10^6~).

Output

Một dòng duy nhất là dãy quẻ may mắn của Hoàng.

Sample input 1

58816
2

Sample output 1

886

Giải thích: Rút quẻ 8 8 6 sẽ nhận được số lớn nhất có thể là 886.

Sample input 2

2357111317192329
6

Sample output 2

7317192329