Doraemon là một chú mèo máy đến từ thế kỷ ~22~ với chiếc túi thần kỳ chứa hàng ngàn món bảo bối độc đáo. Để chuẩn bị cho đợt bảo dưỡng định kỳ tại Xưởng Chế Tạo Mèo Máy, Doraemon quyết định lấy các bảo bối ra để kiểm kê và đánh giá lại mức năng lượng của chúng. Một ngày nọ, khi đang loay hoay sắp xếp trong căn phòng nhỏ, Nobita nhìn thấy Doraemon xếp các món bảo bối thành một hàng dài tăm tắp. Mỗi món bảo bối đều tỏa ra một luồng ánh sáng lấp lánh, tượng trưng cho chỉ số sức mạnh công nghệ của tương lai. Bị cuốn hút, Nobita hỏi Doraemon về ý nghĩa của việc này và được biết rằng đây là "Hàng Bảo Bối Năng Lượng" – một quy trình quản lý nghiêm ngặt để đảm bảo không có món đồ nào bị trục trặc khi sử dụng.

Bị sự kỳ diệu của công nghệ thế kỷ ~22~ hấp dẫn, Nobita xin phép được phụ giúp Doraemon quản lý danh sách bảo bối này thông qua một chiếc máy tính bảng mini. Không phải là sự ghi chép lộn xộn, hệ thống quản lý của Doraemon hoạt động dựa trên một cấu trúc:

• Cấu trúc hàng bảo bối:

  • Doraemon xếp ~N~ món bảo bối thành một hàng ngang, được đánh số thứ tự từ ~1~ đến ~N~ theo chiều từ trái sang phải. Ban đầu, món bảo bối ở vị trí thứ ~i~ có chỉ số năng lượng là một số nguyên dương ~a_i~.

• Quy tắc vận hành hệ thống: Trong quá trình kiểm tra, Doraemon và Nobita sẽ thực hiện ~Q~ thao tác thuộc một trong hai dạng sau:

  • Dạng 1 (Nâng cấp năng lượng): Khi phát hiện bảo bối ở vị trí thứ ~i~ bị hao hụt pin hoặc vừa được nâng cấp linh kiện mới, Doraemon sẽ thay đổi giá trị của phần tử thứ ~i~ thành ~p~.
  • Dạng 2 (Truy xuất bảo bối tối ưu): Để chọn ra món đồ phù hợp giải cứu Nobita khỏi những rắc rối thường ngày, Doraemon cần xét các bảo bối nằm liên tiếp từ vị trí ~L~ đến vị trí ~R~, sau đó tìm số lớn thứ ~K~ trong đoạn ~[L, R]~ đó (khi sắp xếp chỉ số năng lượng của các bảo bối trong đoạn theo thứ tự không tăng).

Vì số lượng bảo bối và các đợt kiểm tra là rất lớn, Nobita đang hoa cả mắt với những con số. Bạn hãy lập trình giúp Doraemon và Nobita xử lý thật nhanh các truy vấn này nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~, lần lượt là số lượng bảo bối và số lượng truy vấn ~(N, Q \leq 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ thể hiện chỉ số năng lượng ban đầu của các bảo bối ~(a_i \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn bắt đầu bằng một số nguyên ~type~:
  • Với ~type = 0~, theo sau là hai số nguyên dương ~i~ và ~p~ – thể hiện truy vấn dạng 1: thay đổi giá trị của phần tử thứ ~i~ thành ~p~ ~(1 \leq i \leq N; p \leq 10^9)~.
  • Với ~type = 1~, theo sau là ba số nguyên dương ~L, R~ và ~K~ – thể hiện truy vấn dạng 2: tìm số lớn thứ ~K~ trong đoạn ~[L, R]~ ~(1 \leq L \leq R \leq N; 1 \leq K \leq R - L + 1)~.

Output

• Với mỗi truy vấn thuộc dạng 2 (~type = 1~), in ra trên một dòng một số nguyên duy nhất là đáp án tìm được.

Example Input

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

Example Output

4
3

Giải thích

• Ban đầu, dãy chỉ số năng lượng của ~5~ bảo bối là: ~[1, 3, 2, 4, 5]~.
• Truy vấn 1 (0 1 5): Thay đổi chỉ số của bảo bối thứ ~1~ thành ~5~. Dãy năng lượng trở thành: ~[5, 3, 2, 4, 5]~.
• Truy vấn 2 (1 1 5 3): Xét đoạn từ ~1~ đến ~5~ là ~[5, 3, 2, 4, 5]~. Khi sắp xếp từ lớn đến bé ta được: ~5, 5, 4, 3, 2~. Giá trị lớn thứ ~K = 3~ trong đoạn này là ~4~.
• Truy vấn 3 (1 2 4 2): Xét đoạn từ ~2~ đến ~4~ là ~[3, 2, 4]~. Khi sắp xếp từ lớn đến bé ta được: ~4, 3, 2~. Giá trị lớn thứ ~K = 2~ trong đoạn này là ~3~.

Ràng buộc

• Subtask ~1~ (~15\%~ số điểm): ~N, Q \leq 10^3~.
• Subtask ~2~ (~15\%~ số điểm): ~N, Q \leq 5 \times 10^4~ và ~K = 1~.
• Subtask ~3~ (~15\%~ số điểm): ~K = R - L + 1~.
• Subtask ~4~ (~15\%~ số điểm): ~N, Q \leq 2\times10^4~ và ~a_i, p \leq 50~.
• Subtask ~5~ (~15\%~ số điểm): ~N, Q \leq 5 \times 10^4~ và ~K \leq 10~.
• Subtask ~6~ (~5\%~ số điểm): ~L = 1; R = N~ và ~a_i, p \leq 10^6~.
• Subtask ~7~ (~5\%~ số điểm): ~L = 1; R = N~.
• Subtask ~8~ (~5\%~ số điểm): ~N, Q \leq 3 \times 10^4~ và ~type_i = 1~.
• Subtask ~9~ (~5\%~ số điểm): ~N, Q \leq 3 \times 10^4~.
• Subtask ~10~ (~5\%~ số điểm): Không có ràng buộc gì thêm.

Edogawa Conan là một thám tử nhí tài ba với bộ óc suy luận sắc bén cùng niềm đam mê giải mã những vụ án hóc búa. Một ngày nọ, văn phòng thám tử Mori nhận được một bức thư thách đấu kỳ lạ từ siêu đạo chích Kaito Kid nhằm báo trước về phi vụ đánh cắp viên đá quý Pandora. Thay vì ghi rõ thời gian và địa điểm, Kid chỉ để lại một danh sách gồm những con số khổng lồ kèm theo lời gợi ý về "Chuỗi số vàng của tự nhiên". Bị cuốn hút bởi thử thách trí tuệ này, Conan lập tức bắt tay vào phân tích và nhận ra rằng chìa khóa của mật mã nằm ở dãy số Fibonacci huyền thoại.

Không phải là những con số ngẫu nhiên, mật mã của Kaito Kid được xây dựng dựa trên một cấu trúc toán học vô cùng chặt chẽ và logic:

• Cấu trúc dãy mật mã:

  • Dãy số Fibonacci được xác định bắt đầu từ chỉ số ~1~ với quy luật kinh điển: ~F_1 = 1, F_2 = 1~, và với mọi ~i \geq 3~ thì ~F_i = F_{i-1} + F_{i-2}~.

• Quy tắc giải mã hệ thống: Trong bức thư, Kaito Kid đưa ra ~Q~ câu đố, mỗi câu đố là một số nguyên dương ~M~:

  • Để mở được từng lớp khóa bảo vệ viên đá quý ứng với số ~M~, Conan cần xét số Fibonacci thứ ~M~.
  • Mật khẩu của lớp khóa chính là số lượng các giá trị Fibonacci phân biệt là ước của ~F_M~.

Thời gian trước giờ hành động của Kaito Kid đang cạn dần trong khi các chỉ số ~M~ lại vô cùng lớn, vượt xa khả năng tính toán thủ công của Tiến sĩ Agasa. Bạn hãy lập trình giúp thám tử Conan giải mã thật nhanh toàn bộ ~Q~ câu đố này nhé!

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ là số lượng câu đố trong bức thư ~(Q \leq 10^6)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~M~ thể hiện chỉ số của số Fibonacci cần giải mã ~(M \leq 10^{18})~.

Output

• Gồm ~Q~ dòng, mỗi dòng in ra một số nguyên duy nhất là số lượng giá trị Fibonacci phân biệt là ước của ~F_M~ tương ứng.

Example Input

2
5
6

Example Output

2
3

Giải thích

• Các số đầu tiên trong dãy Fibonacci là: ~F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8~.
• Với ~M = 5~: Ta có ~F_5 = 5~. Các giá trị thuộc dãy Fibonacci đồng thời là ước của ~5~ gồm: ~1~ và ~5~. Có tất cả ~2~ giá trị phân biệt.
• Với ~M = 6~: Ta có ~F_6 = 8~. Các giá trị thuộc dãy Fibonacci đồng thời là ước của ~8~ gồm: ~1, 2~ và ~8~ (số ~4~ là ước của ~8~ nhưng không thuộc dãy Fibonacci). Có tất cả ~3~ giá trị phân biệt.

Ràng buộc

• Subtask ~1~ (~15\%~ số điểm): ~Q \leq 100~ và ~M \leq 90~.
• Subtask ~2~ (~15\%~ số điểm): ~Q \leq 100~ và ~M \leq 500~.
• Subtask ~3~ (~15\%~ số điểm): ~M \leq 500~.
• Subtask ~4~ (~15\%~ số điểm): ~Q \leq 100~ và ~M \leq 10^5~.
• Subtask ~5~ (~15\%~ số điểm): ~Q \leq 100~ và ~M \leq 10^{12}~.
• Subtask ~6~ (~5\%~ số điểm): ~M \leq 10^7~.
• Subtask ~7~ (~5\%~ số điểm): ~Q \leq 100~ và ~M \leq 10^{14}~.
• Subtask ~8~ (~5\%~ số điểm): ~Q \leq 100~.
• Subtask ~9~ (~5\%~ số điểm): ~Q \leq 1000~.
• Subtask ~10~ (~5\%~ số điểm): ~Q \leq 10^4~.

Monkey D. Luffy và băng hải tặc Mũ Rơm đang dong buồm vượt qua những vùng biển khắc nghiệt của Tân Thế Giới để tiến gần hơn đến hòn đảo cuối cùng Laugh Tale. Một ngày nọ, khi đang quan sát chiếc kim chỉ nam vĩnh cửu (Log Pose) đặc biệt dùng để dẫn đường qua một vùng biển đầy sương mù, hoa tiêu Nami phát hiện ra rằng từ trường của các hòn đảo nơi đây biến đổi theo những dãy số tọa độ khổng lồ. Nếu đi chệch khỏi luồng từ trường ổn định, con tàu Thousand Sunny sẽ lập tức bị cuốn vào những cơn bão xoáy nguy hiểm. Bị cuốn hút bởi hiện tượng kỳ lạ này, nhà khảo cổ học Nico Robin đã đối chiếu với một văn bản cổ và biết được rằng đây là "Vùng Biển Cân Bằng" – nơi chỉ những tọa độ đạt trạng thái hài hòa tuyệt đối mới dẫn lối đến các hòn đảo an toàn.

Để giúp tàu Thousand Sunny vượt qua vùng biển này, Nami quyết định lập bản đồ hàng hải dựa trên cấu trúc toán học của từ trường:

• Cấu trúc tọa độ cân bằng:
  • Mỗi tọa độ trên biển được biểu diễn bằng một số nguyên dương trong hệ thập phân (không tính các chữ số ~0~ vô nghĩa ở đầu). Một số nguyên dương được gọi là số cân bằng nếu trong biểu diễn thập phân của nó, số lượng chữ số chẵn bằng số lượng chữ số lẻ (các chữ số chẵn gồm ~0, 2, 4, 6, 8~; các chữ số lẻ gồm ~1, 3, 5, 7, 9~).

• Quy tắc định vị hải trình: Trước mắt băng Mũ Rơm là ~Q~ vùng biển liên tiếp cần phải khảo sát:
  • Với mỗi vùng biển thứ ~i~, Nami xác định được phạm vi tọa độ trải dài từ ~L~ đến ~R~.
  • Nhiệm vụ của cô là phải đếm số lượng số cân bằng thuộc đoạn ~[L, R]~ để ước tính số lượng hải đảo an toàn có thể neo đậu.

Vì tọa độ ở Tân Thế Giới là những con số cực kỳ khổng lồ (có thể lên tới hàng trăm nghìn chữ số), kết quả đếm được cũng sẽ rất lớn. Do đó, Nami chỉ cần biết phần dư của số lượng tìm được khi chia cho ~10^9 + 7~. Bạn hãy lập trình giúp hoa tiêu Nami tính toán thật nhanh các thông số này để băng Mũ Rơm tiếp tục cuộc phiêu lưu nhé!

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ là số lượng vùng biển cần khảo sát ~(Q \leq 1000)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L~ và ~R~ cách nhau bởi một khoảng trắng thể hiện phạm vi tọa độ của vùng biển ~(1 \leq L \leq R \leq 10^{100000})~.

Output

• Gồm ~Q~ dòng, mỗi dòng in ra một số nguyên duy nhất là số lượng số cân bằng trong đoạn ~[L, R]~ tương ứng sau khi chia lấy dư cho ~10^9 + 7~.

Example Input

1
1 20

Example Output

5

Giải thích

• Trong đoạn từ ~1~ đến ~20~, các số có ~1~ chữ số (từ ~1~ đến ~9~) đều chỉ có ~1~ chữ số chẵn hoặc ~1~ chữ số lẻ nên không có số nào cân bằng.
• Xét các số có 2 chữ số từ ~10~ đến ~20~, các số có đúng ~1~ chữ số chẵn và ~1~ chữ số lẻ bao gồm: ~10, 12, 14, 16, 18~.
• Vậy có tất cả ~5~ số cân bằng trong đoạn ~[1, 20]~.

Ràng buộc

Gọi ~|S|~ là số lượng chữ số trong biểu diễn thập phân của ~S~.

• Subtask ~1~ (~15\%~ số điểm): ~Q \leq 100~ và ~R \leq 1000~.
• Subtask ~2~ (~15\%~ số điểm): ~R \leq 10^6~.
• Subtask ~3~ (~15\%~ số điểm): ~R \leq 10^9~.
• Subtask ~4~ (~15\%~ số điểm): ~L = 1, R = 10^k~ ~(k \leq 10)~.
• Subtask ~5~ (~15\%~ số điểm): ~R \leq 10^{18}~.
• Subtask ~6~ (~5\%~ số điểm): ~L = 1, R = 10^k~ ~(k \leq 10^4)~.
• Subtask ~7~ (~5\%~ số điểm): ~Q \leq 100~ và ~|L|, |R| \leq 100~.
• Subtask ~8~ (~5\%~ số điểm): ~Q \leq 100~ và ~|L|, |R| \leq 1000~.
• Subtask ~9~ (~5\%~ số điểm): ~Q \leq 100~ và ~|L|, |R| \leq 10^4~.
• Subtask ~10~ (~5\%~ số điểm): ~Q \leq 100~.

Son Goku là một chiến binh Saiyan quả cảm với niềm đam mê võ thuật bất tận và trái tim luôn sẵn sàng bảo vệ hòa bình vũ trụ. Trong cuộc hành trình tìm kiếm Bảy Viên Ngọc Rồng trên hành tinh Namek để hồi sinh những người đồng đội đã ngã xuống, Goku phải di chuyển từ căn cứ xuất phát của nhóm Bulma đến vùng đất linh thiêng của Quốc Trưởng Guru. Qua chiếc máy Radar Ngọc Rồng do Bulma chế tạo, toàn bộ địa hình hành tinh Namek hiện lên như một mạng lưới các hòn đảo liên kết chặt chẽ với nhau. Tuy nhiên, đội quân của bạo chúa Frieza đang ráo riết tuần tra và sẵn sàng phong tỏa bất kỳ khu vực nào để chặn đường Goku.

Để giúp Goku giữ sức cho trận chiến quyết định, Bulma quyết định lập trình một hệ thống dẫn đường thông minh trên Radar dựa trên cấu trúc bản đồ:

• Cấu trúc bản đồ hành tinh Namek:
  • Hệ thống địa hình gồm ~N~ khu vực được đánh số thứ tự từ ~1~ đến ~N~, trong đó khu vực ~1~ là căn cứ xuất phát và khu vực ~N~ là nơi ở của Quốc Trưởng Guru.
  • Có ~M~ tuyến đường bay hai chiều nối giữa các khu vực. Tuyến đường thứ ~i~ kết nối trực tiếp hai khu vực ~u~ và ~v~ với khoảng cách di chuyển là một số nguyên dương ~w~.

• Quy tắc cảnh báo của Radar: Trước sự truy lùng của quân đoàn Frieza, Bulma đặt ra ~Q~ kịch bản khẩn cấp cần phải tính toán trước:
  • Mỗi kịch bản được đại diện bởi một số nguyên dương ~x~, giả định rằng khu vực ~x~ (cùng toàn bộ các tuyến đường kết nối trực tiếp với ~x~) đã bị Frieza phong tỏa hoàn toàn và Goku không thể đi qua đó.
  • Nhiệm vụ của hệ thống là phải tìm ra độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~ nếu loại bỏ đỉnh ~x~ khỏi đồ thị.

Tình thế trên hành tinh Namek đang vô cùng cấp bách khi khí của Frieza ngày càng tiến lại gần. Bạn hãy lập trình giúp Bulma và Son Goku tìm ra lộ trình tối ưu cho toàn bộ ~Q~ kịch bản này nhé!

Input

• Dòng đầu tiên chứa ba số nguyên dương ~N, M~ và ~Q~, lần lượt là số lượng khu vực, số lượng tuyến đường bay và số lượng kịch bản giả định ~(N,Q \leq 10^5; M \leq 2\times10^5)~.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~u, v~ và ~w~ thể hiện tuyến đường hai chiều nối giữa đỉnh ~u~ và đỉnh ~v~ có trọng số ~w~ ~(1 \leq u, v \leq N; w \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~x~ thể hiện khu vực bị loại bỏ trong kịch bản tương ứng ~(1 \leq x \leq N)~.

Output

• Gồm ~Q~ dòng, mỗi dòng in ra một số nguyên duy nhất là độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~ khi loại bỏ đỉnh ~x~ tương ứng. Nếu không tồn tại đường đi, in ra ~-1~.

Example Input

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

Example Output

7
8

Giải thích

• Ban đầu, đồ thị có ~2~ lộ trình chính từ đỉnh ~1~ đến đỉnh ~5~:
  • Lộ trình ~1 \rightarrow 2 \rightarrow 4 \rightarrow 5~ có tổng trọng số là ~3 + 3 + 2 = 8~.
  • Lộ trình ~1 \rightarrow 3 \rightarrow 5~ có tổng trọng số là ~5 + 2 = 7~.
• Truy vấn 1 (2): Nếu loại bỏ đỉnh ~2~, lộ trình đi qua đỉnh ~2~ bị chặn. Đường đi ngắn nhất từ ~1~ đến ~5~ lúc này là ~1 \rightarrow 3 \rightarrow 5~ với tổng trọng số là ~7~.
• Truy vấn 2 (3): Nếu loại bỏ đỉnh ~3~, lộ trình đi qua đỉnh ~3~ bị chặn. Đường đi ngắn nhất từ ~1~ đến ~5~ lúc này là ~1 \rightarrow 2 \rightarrow 4 \rightarrow 5~ với tổng trọng số là ~8~.

Ràng buộc

• Subtask ~1~ (~15\%~ số điểm): ~N \leq 100~ và ~Q = 1~.
• Subtask ~2~ (~15\%~ số điểm): ~N \leq 100~ và ~Q \leq 100~.
• Subtask ~3~ (~15\%~ số điểm): ~N \leq 1000~ và ~Q = 1~.
• Subtask ~4~ (~15\%~ số điểm): ~N \leq 1000~ và ~Q \leq 100~.
• Subtask ~5~ (~15\%~ số điểm): Đồ thị đã cho là một cây.
• Subtask ~6~ (~5\%~ số điểm): ~Q \leq 100~ và ~w = 1~.
• Subtask ~7~ (~5\%~ số điểm): ~N \leq 2000~ và ~Q \leq 10^5~.
• Subtask ~8~ (~5\%~ số điểm): ~N \leq 5 \times 10^4~ và ~Q \leq 1000~.
• Subtask ~9~ (~5\%~ số điểm): Số giá trị ~x~ khác nhau trong tất cả các truy vấn ~\leq 100~ và ~N, Q \leq 10^5~.
• Subtask ~10~ (~5\%~ số điểm): Không có ràng buộc gì thêm.