Cho một số nguyên dương \(X\). Một số \(Y\) được gọi là đồng môn với \(X\) nếu \(Y\) được tạo ra bằng cách tráo đổi vị trí các kí tự trong \(X\). Hãy tìm số đồng môn nhỏ nhất lớn hơn \(X\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(X\).

Output

• Một số nguyên dương là kết quả. Nếu không tồn tại kết quả thì in ra \(0\).

Scoring

• \(1 \leq X \leq 10^6\)

Example

123

132

Cho \(N\) đường thẳng có dạng \(Ax+By+C=0\) trên mặt phẳng tọa độ. Biết rằng không có ba đường thẳng nào cùng giao nhau ở 1 điểm. Bạn hãy tính số lượng tam giác tạo thành từ các đường thẳng. Vì kết quả có thể rất lớn, đáp số cuối cùng sẽ modulo \(10^9+7\).

Input

• Dòng đầu tiên là số nguyên dương \(N\), là số lượng đường thẳng. \((1 \leq N \leq 3 \times10^5)\)
• \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(A, B, C\) (Các giá trị tuyệt đối không vượt quá \(10^9\))

Output

• Một dòng duy nhất là số lượng tam giác tạo thành.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 5000\)
• Subtask \(2\) (\(60\%\) số điểm): không có điều kiện gì thêm

Example

6
0 1 0
-5 3 0
-5 -2 25
0 1 -3
0 1 -2
-4 -5 29 

10

Cho một ma trận có kích thước N x M chỉ gồm các số 0 và 1. Nhiệm vụ của bạn là tìm một ma trận con thỏa mãn các điều kiện sau:

Input

• Dòng thứ nhất là hai số nguyên dương N, M là kích thước ma trận

• N dòng tiếp theo, mỗi dòng gồm M ký tự '0' hoặc '1'

Output

• Một dòng duy nhất là độ dài cạnh ma trận lớn nhất thỏa mãn điều kiện trên, nếu không tồn tại xuất -1.

Constants

\(1 \leq N, M \leq 300\)

Example

3 3
100
011
101 

2

Kuzan có một bài toán về nhà như sau: Cho một số nguyên dương \(X\), ta chia \(X\) thành từng nhóm sao cho mỗi nhóm chỉ bao gồm một loại chữ số. Giá trị của số \(X\) được tính bằng tổng giá trị các nhóm, mà tổng giá trị các nhóm được tính bằng giá trị của chữ số nhóm nhân với bình phương độ dài nhóm. Ví dụ: số \(3332144\) có giá trị là \(46\) vì ta chia thành các nhóm \(333, 2, 1, 44\) với tổng là \(3*3^2+2*1^2+1*1^2+4*2^2 = 46\).

Tuy nhiên, vì cảm thấy còn dễ, Kuzan tự đặt ra bài toán mới cho mình: Tính tổng các giá trị của các số nguyên trong đoạn \([L;R]\). Bạn hãy cùng Kuzan giải bài toán này.

Input

• Một dòng duy nhất là hai số nguyên dương \(L, R (1 \leq L \leq R \leq 10^{15})\).

Output

• Một dòng duy nhất là đáp số bài toán.

Example

1 9

45

Cho một bảng có số hàng và số cột là vô hạn. Các giá trị của các ô trong bảng được tính theo các quy tắc sau: Với \(i\) là chỉ số hàng, \(j\) là chỉ số cột, ta có:

• \(A[i][1] = i\)
• \(A[i][j] = A[i][j-1] + INV(A[i][j-1])\) \(\forall j > 1\)

Với \(INV(A)\) là hàm đảo ngược số \(A\). Ví dụ, \(INV(104) = 401, INV(200) = 002 = 2\).

Các số đầu tiên của bảng:

Cho \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên dương \(A\) và \(B\). Bạn hãy đếm số lần xuất hiện các số trong khoảng \([A,B]\) trên bảng đó.

Input

• Dòng đầu tiên là số nguyên dương \(Q\), số lượng truy vấn \((1 \le Q \le 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng là hai số nguyên dương \(A,B (1 \le A \le B \le 10^{10})\)

Output

• Gồm \(Q\) dòng, mỗi dòng là kết quả của truy vấn.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(A,B\) \(\leq\) \(10^6\)
• Subtask \(2\) (\(50\%\) số điểm): không có điều kiện gì thêm

Example

2
1 3
4 8

4
11