Cho dãy số có quy luật như sau: ~1,2,2,3,3,3,4,4,4,4,5,5,…~ Cho một số tự nhiên ~N~, hãy tìm số thứ ~N~ của dãy số trên (các số được đánh thứ tự từ ~1~).

Input: nhập vào từ file "DSCQL.INP"

Số nguyên dương ~N~ ~(N ≤ 10^{15})~.

Output: ghi ra file "DSCQL.OUT"

In ra kết quả của bài toán.

Scoring

• Subtask 1 [60%]: ~N ≤ 10^{6}~;
• Subtask 2 [20%]: ~N ≤ 10^{10}~;
• Subtask 3 [20%]: Không có ràng buộc gì thêm.

Examples

Input1

5

Output1

3

Cho một xâu ~S~ gồm các kí tự số. Hãy đếm xem có bao nhiêu xâu con chia hết cho ~4~ (xâu con có thể bắt đầu bằng ~0~).

Input:

Xâu ~S~ có độ dài không quá ~10^6~.

Output:

In ra kết quả của bài toán.

Scoring

• Subtask 1 [60%]: Xâu ~S~ có độ dài không quá ~100~.
• Subtask 2 [40%]: Không có ràng buộc gì thêm.

Examples

Input1

08

Output1

3

Giải thích

~0, 8, 08~

Input2

13085

Output2

5

Do tuyển tin bạn nào cũng thích chơi điện tử nên thầy Tùng phải đặt gấp thuốc chống nghiện điện tử của Marisa.

Marisa có ~n~ lọ thuốc, mỗi lọ thuốc có dạng hình trụ có chiều cao là ~h~ và bán kính đáy là ~r~. Thuốc có dạng lỏng và coi như vỏ lọ thuốc không đáng kể.

~m~ bạn học sinh sẽ quyết định mỗi bạn sẽ uống một lượng thuốc giống nhau là ~X~. Lần lượt từng bạn sẽ chọn chính xác một lọ thuốc và uống một lượng ~X~ trong lọ nếu còn đủ. Để hiệu quả chống nghiện tốt nhất, ~X~ phải là lớn nhất, hãy giúp các bạn học sinh tìm giá trị này để tất cả các bạn cùng nhau cai nghiện thành công.

Input: nhập vào từ file "CAINGHIEN.INP"

• Dòng đầu tiên gồm hai số nguyên ~n,m~.
• ~n~ dòng tiếp theo, mỗi dòng gồm hay số nguyên ~h,r~.

Output: ghi ra file "CAINGHIEN.OUT"

• In ra một số thực là đáp án của bài toán. Đáp án được coi là đúng khi chênh lệch với đáp án của hệ thống không quá ~10^{-6}~.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le m \le 10^9~.
• ~1 \le h,r \le 10^4~.

Ví dụ

Input:

3 4
3 2
1 1
2 3

Output:

18.849556

Giới hạn

• Subtask 1 (20% số điểm): ~m = 2~.
• Subtask 2 (30% số điểm): ~n,m \le 8~.
• Subtask 3 (50% số điểm): Không có giới hạn gì thêm.

Cho hai số nguyên dương ~n~ và ~k~.

Ta có thể xây dựng một dãy số nguyên dương ~a~ gồm ~n~ phần tử: ~a_1,a_2,...,a_n~ sao cho với mọi ~1 \le i \le n~ thỏa mãn điều kiện ~a_i \in [1,k]~.

Gọi ~g(a)~ là ước chung lớn nhất của dãy số ~a~.

Nhiệm vụ của bạn chính là tính tổng ~g(a)~ của mọi dãy số có thể xây dựng (có ~k^n~ dãy số như vậy).

Vì kết quả có thể rất lớn, hãy in nó ra theo module ~10^9+7~.

Input: nhập vào từ file "SUMGCD.INP"

• Gồm một dòng chứa hai số nguyên dương ~n,k~ ~(1 \le n \le 10^9, 1 \le k \le 10^6)~.

Output: ghi ra file "SUMGCD.OUT"

• In ra kết quả theo module ~10^9+7~.

Subtask

• Subtask ~1~ ~(20\%)~: ~n,k \le 7~
• Subtask ~2~ ~(20\%)~: ~n \le 10^5, k = 4~
• Subtask ~3~ ~(25\%)~: ~n \le 10^5, k \le 20~
• Subtask ~4~ ~(20\%)~: ~k \le 10^5~
• Subtask ~5~ ~(15\%)~: Không giới hạn gì thêm.

Ví dụ

Sample Input 1

1  5

Sample Output 1

15

Sample Input 2

5 4

Sample Output 2

1060

Sample Input 3

3 2

Sample Output 3

9

Giải thích

Ở ví dụ ~3~ ta có:

• ~g([1,1,1]) = 1~
• ~g([1,1,2]) = 1~
• ~g([1,2,1]) = 1~
• ~g([1,2,2]) = 1~
• ~g([2,1,1]) = 1~
• ~g([2,1,2]) = 1~
• ~g([2,2,1]) = 1~
• ~g([2,2,2]) = 2~

Kết quả thu được là ~9~.

Một mê cung được biểu diễn bằng một bảng vuông ~A~ kích thước ~n \times n~ ô, các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải, ô nằm giao giữa hàng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Một số ô của bảng có chướng ngại vật và được đánh dấu là ~1~, những ô còn lại là các ô trống và được đánh dấu ~0~. Một robot chỉ di chuyển trong bảng và có thể đi từ ô trống này sang ô trống khác lân cận kề cạnh. Một đường đi của robot giữa hai ô trống là một dãy các ô lân cận từ ô này tới ô kia và không có ô nào đi qua quá một lần, độ dài của đường đi được tính bằng số lượng ô mà robot đi qua. Bảng ~A~ là mê cung nên giữa hai ô trống bất kỳ của bảng có đúng một đường đi giữa chúng.

Hãy xử lí ~q~ thao tác, mỗi thao tác thuộc một trong hai dạng sau:

• Thao tác dạng: ~1~ ~u~ ~v~, thao tác này sẽ thực hiện đặt chướng ngại vật vào ô ~(u, v)~. Chú ý rằng, sau khi thực hiện thao tác loại này, bảng ~A~ có thể không còn là mê cung nữa;
• Thao tác dạng: ~2~ ~u~ ~v~ ~x~ ~y~, thao tác này cần tính độ dài đường đi từ ô ~(u, v)~ đến ô ~(x, y)~. Nếu không tồn tại đường đi đưa ra ~-1~.

Input: nhập vào từ file "KPMC.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa xâu ~n~ kí tự ~[0,1]~ mô tả hàng ~i~ của ~A~.
• Dòng thứ ~j~ trong ~q~ dòng tiếp theo mô tả thao tác thứ ~j~.

Output: ghi ra file "KPMC.OUT"

• Gồm một số dòng tương ứng là các câu trả lời cho thao tác tìm độ dài đường đi giữa hai ô.

Subtask

• Subtask ~1~ ~(30\%)~: ~n,q \le 100~.
• Subtask ~2~ ~(30\%)~: ~n \le 1000~ và chỉ có thao tác loại ~2~.
• Subtask ~3~ ~(40\%)~: ~n \le 1000, q \le 10^5~.

Ví dụ

Sample Input 1

3 3
000
110
000
2 1 1 3 1
1 2 3
2 1 1 3 1

Sample Output 1

7
-1