Ngoài lề một tí

Nếu bạn là thí sinh thi VNOI OI'09, đọc đến đây chắc hẳn bạn đang mừng lắm. Bởi vì mãi mới tìm thấy bài đồ thị "tủ" để kiếm điểm. Chắc chắn bạn sẽ càng mừng hơn nếu như tôi nói với bạn rằng bài mà bạn chuẩn bị đọc ở đây không yêu cầu thuật toán đồ thị nào cả mà chỉ hỏi về phần mà ai cũng biết đó là biểu diễn đồ thị.

Đề bài

Chú ý: đồ thị trong bài này là đồ thị có hướng.

Bạn cần viết chương trình xử lý các yêu cầu sau:

• NEW ~n~ ~k~, với ~k = 0~ hoặc ~k = 1~ (khởi tạo ~1~ đồ thị mới với ~n~ đỉnh, nếu ~k = 0~ thì là đồ thị rỗng, nếu ~k = 1~ thì là đồ thị đầy đủ, đồ thị đầy đủ này bao gồm ~n^{2}~ cạnh, nghĩa là bao gồm cả các vòng ~(u, u)~ với ~1 \leq u \leq n)~.
• ADD ~u~ ~v~ (thêm cạnh ~(u, v)~ nếu chưa có).
• DEL ~u~ ~v~ (xóa cạnh ~(u, v)~ nếu có).
• ANY (xóa một cạnh bất kì trong đồ thị nếu có).
• EDG ~u~ ~v~ (kiểm tra xem có cạnh ~(u, v)~ hay không).

Bạn hãy lập trình xử lý bài toán sau đây:

• Nhập vào ~M~ yêu cầu, hãy thực hiện lần lượt từng yêu cầu.
• Đối với những yêu cầu ANY, in ra cạnh bị xóa. Nếu không có cạnh nào thì in ra ~- 1~.
• Đối với những yêu cầu EDG ~u~ ~v~, in ra YES/NO tương ứng với có hay không có cạnh ~(u, v)~.

Input

• Gồm nhiều dòng, mỗi dòng ghi một yêu cầu cần xử lý. Dòng cuối cùng ghi "END" báo hiệu kết thúc dữ liệu. Số yêu cầu cần xử lý không quá ~10^{6}~.

Với yêu cầu dạng NEW, ta luôn có ~1 \leq n \leq 1000~.

Dữ liệu đảm bảo yêu cầu đầu tiên luôn là yêu cầu dạng NEW và với các yêu cầu ADD, DEL, EDG, ~1 \leq u~, ~v \leq n~.

Output

Tương ứng với mỗi yêu cầu dạng ANY hay EDG là một dòng ghi kết quả.

• Đối với yêu cầu dạng ANY, ghi ra hai số ~u~, ~v~ cho biết bạn muốn xóa cạnh ~(u, v)~.
• Đối với yêu cầu dạng EDG, ghi ra "YES" hoặc "NO" tương ứng với việc đồ thị còn cạnh ~(u, v)~ hay không.

Sample Input

NEW 4 0
ADD 1 2
ADD 2 3
ANY
EDG 1 2
END

Sample Output

1 2
NO

Note

Với test ví dụ ở trên, kết quả sau đây cũng hợp lệ:

2 3
YES

Hôm nay, anh Conankudo ngoan của chúng ta đang bị ốm, thế mà anh ta lại phải căng đầu để chiến đấu với ~1~ lời thách đố từ anh Quỳnh. Conankudo không thể giải được vì anh ta đang lâm trọng bệnh, các bạn hãy thử giúp anh ta xem.

Sản phẩm số của ~1~ số nguyên dương là kết quả khi lấy tích của các chữ số tạo nên số nguyên đó. Ví dụ, sản phẩm số của ~2612~ là ~2 \times 6 \times 1 \times 2 = 24~.

Sản phẩm "bản thân" của ~1~ số là tích của nó với sản phẩm số. Ví dụ sản phẩm bản thân của ~2612~ là ~2612 \times 24 = 62688~.

Viết chương trình, biết ~2~ số nguyên dương ~A~ và ~B~, tính số số nguyên dương có sản phẩm bản thân trong đoạn ~[A;B]~.

Input

Dòng duy nhất gồm ~2~ số nguyên ~A~ và ~B~ ~(1 \le A \le B \le 10^{18})~

Output

Chỉ gồm ~1~ số nguyên, là số số nguyên dương có kết quả trong khoảng ~[A;B]~.

Sample Input

20 30

Sample Output

2

Làng Đo Đo là một ngôi làng nhỏ nằm ven con sông Kiếp Bạc. Làng gồm ~N~ xóm, các xóm được nối với nhau bởi ~N-1~ con đường hai chiều, sao cho từ một xóm có thể đi tới một xóm khác bất kỳ.

Có dịp về làng Đo Đo chơi vài ngày, Đông định cùng cô bạn Rùa của mình đi chơi khắp làng xóm để thỏa nỗi nhớ mong xa cách. Nhưng thật không may, một trận mưa lớn vừa xảy ra ở làng, và do hệ thống thoát nước chống ngập của làng Đo Đo không được trùng tu bảo dưỡng, một số con đường của làng có thể đã bị ngập.

Đông muốn cùng cô bạn Rùa đi chơi càng xa càng tốt (để đỡ bị cô Út Huệ hay bà ngoại Rùa gọi về), vì vậy anh ta muốn biết khoảng cách trung bình từ nhà của Rùa (là địa điểm xuất phát), tới nơi xa nhất tới được. Biết nhà của rùa nằm ở xóm ~1~, và độ dài mỗi con đường đều là ~1~.

Do đã sơ suất để quên Ipod, Itouch, Iphone, Ipad, Iwatch, ...ở Sài Gòn, anh chàng Đông cần nhờ tới sự giúp đỡ của các thí sinh VM15.

Input

Dòng đầu tiên gồm ~1~ số nguyên dương ~N~, là số xóm trong làng.

~N-1~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u~ ~v~ ~p~ mô tả một con đường, bao gồm ~2~ xóm đầu cuối ~(u~, ~v)~ và xác suất ~(p)~ con đường không bị ngập sau trận mưa (tính theo phần trăm).

Output

In ra khoảng cách trung bình từ nhà của Rùa (xóm ~1~) tới xóm xa nhất có thể tới được, với ít nhất ~6~ chữ số sau dấu phẩy.

Giới hạn

• Trong tất cả các test ~0 \leq p \leq 100~
• Subtask1: ~N \leq 15~ ~(25\%~ số điểm)
• Subtask2: ~N \leq 2207~ ~(31.25\%~ số điểm)
• Subtask3: ~N \leq 97722, p \leq 97~ ~(43.75\%~ số điểm)

Sample Input 1

4
1 2 50
2 3 50
1 4 50

Sample Output 1

1.000000000

Sample Input 2

3
1 2 33
1 3 66

Sample Output 2

0.772200000

Note

Test Ví dụ 1

Nếu ~2~ con đường (~1~, ~2~) và (~2~, ~3~) đều không bị ngập (xác suất ~25\%~), độ dài đường đi là ~2~.

Nếu ~2~ con đường (~1~, ~2~) và (~1~, ~4~) đều bị ngập (xác suất ~25\%~), độ dài đường đi là ~0~.

Các trường hợp còn lại (xác suất ~50\%~), độ dài đường đi là ~1~.

Vậy độ dài trung bình là ~(0.25 \times 2 + 0.25 \times 0 + 0.5 \times 1) = 1~.

Test Ví dụ 2

Nếu ~1~ trong ~2~ con đường ~k~ bị ngập, độ dài đường đi là ~1~, ngược lại độ dài đường đi là ~0~.

Xác suất để cả ~2~ con đường đều bị ngập là ~(100\%-33\%) \times (100\%-66\%) = 22.78\%~