Cho ba số nguyên không âm \(a, b, c\) và hai phép toán cộng (+) và nhân (\(\times\)). Hãy điền số vào ô hình vuông và phép toán vào ô hình tròn theo quy tắc dưới đây để nhận được một biểu thức có giá trị lớn nhất.

• Mỗi một trong ba số \(a, b, c\) được điền vào đúng \(1\) ô hình vuông bất kì;
• Mỗi ô hình tròn điền một phép toán cộng hoặc nhân;

Yêu cầu: In ra giá trị lớn nhất của biểu thức có thể tạo ra.

Input

Gồm một dòng duy nhất chứa ba số nguyên không âm \(a, b, c\) \((a, b, c \leq 10^{6})\), các số cách nhau một dấu cách.

Output

Gồm một số nguyên duy nhất là giá trị lớn nhất của biểu thức tìm được.

Example

Input

2 1 4

Output

9

Explanation

\(1 + 4 \times 2 = 9\)

Từ dãy số tự nhiên \(1; 2; 3; ...; N\) người ta sắp xêp lại dãy số này theo số dư trong các phép chia các số hạng của dãy số cho một số lự nhiên \(K\) là ước nào đó của \(N\) như sau:

• Đoạn thứ nhất gồm tất cả các số chia hết cho \(K\);
• Đoạn thứ hai gồm tất cả các sổ chia \(K\) dư 1;
• Đoạn thứ ba gồm tất cả các số chia \(K\) dư 2;
• ...
• Đoạn cuối cùng gồm tất cà các số chia \(K\) dư \(K\) - 1.

Các số hạng trong mỗi đoạn cũng được sắp xếp theo chiêu tăng dần.

Ví dụ: Với \(N = 12\) và \(K = 4\) sau khi sắp xếp ta có dãy số sau: \(4; 8; 12; 1; 5; 9; 2; 6; 10; 3; 7; 11\)

Yêu cầu: Cho trước 3 số nguyên dương \(N; K; M\) (với \(K\) là ước của \(N\) và \(M < N\)). Tìm số hạng thử \(M\) của dãy đã sắp xếp.

Input

• 3 số nguyên dương \(N; K; M\) (\(N \le 10^{16}; K \le 10^9; K\) là ước của \(N\); \(M < N\)) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Output

• Ghi ra số hạng thứ M của dãy số theo yêu cầu.

Scoring

• Có 20% test ứng với \(N \le 10^2\);
• Có 30% test ứng với \(10^2 < N \le 10^6\);
• Có 30% test ứng với \(10^6 < N \le 10^9\);
• Có 20% test ứng với \(10^9 < N \le 10^{16}\).

Sample Tests

Input

12 4 6

Output

9

Cho hai dãy \(a\) và \(b\) gồm \(n\) phần tử nguyên dương. Bạn được nhận thêm một số nguyên dương \(k\), hãy đếm số cặp \((i,j)\) \((1 \le i,j \le n)\) sao cho \(\overline{a_ib_j}\) \(\vdots\) \(k\).

Nói cách khác, hãy đếm số cặp \((i,j)\) sao cho số nguyên dương \(X\) được tạo bởi cách viết liền \(a_i\) và \(b_j\) với nhau chia hết cho số nguyên dương \(K\) cho trước.

Ví dụ:

• \(a_i = 5, b_j = 77 \Rightarrow X = 577\)
• \(a_i = 66, b_j = 99 \Rightarrow X = 6699\)

Input

• Dòng đầu tiên gồm số hai nguyên dương \(n\) và \(k\) \((1 \le n,k \le 3 \times 10^5)\)
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((1 \le a_i \le 3 \times 10^5)\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(b_1,b_2,...,b_n\) \((1 \le b_i \le 3 \times 10^5)\).

Output:

• Gồm một dòng in ra số cặp \((i,j)\) thỏa mãn.

Subtask:

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 2000\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_i,b_j \le 2000\) \(\forall i,j \in [1,n]\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 3
1 4 3 6
11 2 4 21 

Sample Output 1

6

Explanation 1

Có các cặp sau:

• \((1,1) = 111\)
• \((1,2) = 12\)
• \((2,1) = 411\)
• \((2,2) = 42\)
• \((3,4) = 321\)
• \((4,4) = 621\)

Bạn được cho một mảng \(a\) gồm \(n\) phần tử nguyên dương phân biệt. Ở mỗi bước, bạn có thể chọn ra một số nguyên dương \(x\), sao cho \(x\) không xuất hiện trong dãy \(a\), sau đó thêm số \(x\) vào đuôi của \(a\).

Để tránh biến đây thành một chuỗi hành động dài vô tận, bạn quyết định sẽ dừng lại khi tổng của các phần tử trong dãy \(a\) lớn hơn hoặc bằng giá trị \(k\) cho trước.

Bạn muốn chơi trò chơi này lâu nhất có thể (hơi ngược đời nhỉ), vậy nên hãy tìm ra chiến thuật tốt nhất để chơi được nhiều lượt nhất!

Input

• Dòng đầu chứa hai số nguyên dương \(n,k\) miêu tả độ dài của dãy \(a\) ban đầu và số \(k\) cho trước \((1 \le n \le 2 \times 10^5, 1 \le k \le 10^{18})\).
• Dòng thứ hai chứa \(n\) số nguyên dương phân biệt \(a_1,a_2,...,a_n\) \((1 \le a_i \le 10^{12})\).

Output

• Gồm một số nguyên dương là số lượt chơi lâu nhất có thể nếu bạn chơi tối ưu.

Subtask

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 100, k \le 10^6\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 1000, k \le 10^9\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^5, k \le 10^{12}\)
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm

Sample input 1

3 15
1 3 5

Sample output 1

2

Sample input 2

5 35
1 4 2 6 12

Sample output 2

3

Explanation:

• Ở ví dụ thứ nhất, bạn chỉ có thể chơi \(2\) lượt, giả sử bạn lần lượt thêm vào \(2\), dãy sau đó trở thành \([1,3,5,2]\), và ở lượt sau bạn thêm vào \(4\), dãy trở thành \([1,3,5,2,4]\). Lúc này dãy đã vừa đủ có tổng bằng \(k=15\) nên sẽ không được thêm nữa.

Hàng cây gồm \(n\) cây, được đánh số từ \(1\) đến \(n\) từ trái qua phải. Ở vị trí thứ \(i\), Quân chỉ được phép trồng cây có độ cao không quá \(h_i\).

Quân muốn tìm một loại cây có độ cao là số nguyên \(H\) \((H \le h_1, H \le h_n)\) và trồng vào một số vị trí thích hợp, biết rằng cậu chắc chắn sẽ trồng cây vào vị trí thứ \(1\) và thứ \(n\).

Nếu cây ở vị trí thứ \(i\) bị đổ, nó sẽ làm các cây ở vị trí trong khoảng \([i+1, i+H]\) đổ theo.

Hãy giúp Quân tính xem, độ cao \(H\) nhỏ nhất có thể là bao nhiêu, sao cho nếu Quân chặt đổ cây ở vị trí thứ \(1\) thì cây ở vị trí thứ \(n\) cũng bị đổ theo.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((n \leq 10^7)\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(h_1, h_2, \ldots, h_n\) \((h_i \leq n)\).

Dữ liệu bảo đảm tồn tại một đáp án hợp lệ.

Output

• In ra một số nguyên dương là kết quả của bài toán.

Subtask

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 1000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^6\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Sample Input 1

10 
10 1 2 0 3 4 5 0 2 10

Sample Output 1

2

Explanation 1

Quân trồng cây độ cao \(2\) ở các vị trí \(1, 3, 5, 7, 9, 10\).

Biểu thức ngoặc là xâu chỉ gồm các kí tự '(', ')', '[', ']', '{', '}'. Biểu thức ngoặc đúng và bậc của biểu thức ngoặc đúng được định nghĩa một cách đệ quy như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng \(0\).
• Nếu \(A\) là biểu thức ngoặc đúng có bậc bằng \(k\) thì (A), [A], {A} cũng là một biểu thức ngoặc đúng có bậc bằng \(k \; + \; 1\).
• Nếu \(A\) và \(B\) là hai biểu thức ngoặc đúng và có bậc tương ứng là \(k_1\) và \(k_2\) thì \(AB\) cũng là một biểu thức ngoặc đúng có bậc bằng \(\text{max}(k_1, \; k_2)\).

Ví dụ, ()[()] là một biểu thức ngoặc đúng có bậc bằng \(2\) còn {()[{}]} là một biểu thức ngoặc đúng và có bậc bằng \(3\).
Ta sẽ xét hai trường hợp sau:

• \(T \; = \; 1\): biểu thức ngoặc chỉ gồm kí tự '(' và ')'.
• \(T \; = \; 2\): biểu thức ngoặc gồm kí tự '(', ')', '[', ']', '{', '}'.

Với hai số nguyên \(N\), \(K\), người ta tiến hành tạo ra tất cả các biểu thức ngoặc đúng có độ dài \(N\) và bậc không vượt quá \(K\). Sắp xếp các biểu thức ngoặc theo thứ tự từ điển, chú ý rằng '(' < ')' < '[' < ']' < '{' < '}'.

Cho biểu thức ngoặc đúng \(S\), hãy tìm thứ tự của biểu thức ngoặc đúng \(S\).

Input:

• Dòng thứ nhất chứa số nguyên \(T\) \((1 \leq T \leq 2)\).
• Dòng thứ hai chứa hai số nguyên \(N\) và \(K\) \((N \leq 3000 \; K \leq N / 2)\).
• Dòng thứ ba chứa \(N\) kí tự của biểu thức ngoặc \(S\).

Output:

• Thứ tự của dãy ngoặc \(S\) lấy dư cho \(10^9 + 7\).

Sample test

Input:

2
8 4
{}(({}))

Output:

1008

Subtask:

• Subtask \(1\) (\(20\%\) số điểm): \(T \; = \; 2, \; N \; \leq \; 10\).
• Subtask \(2\) (\(15\%\) số điểm): \(T \; = \; 1, \; S \; =\) ()()()...
• Subtask \(3\) (\(15\%\) số điểm): \(T \; = \; 2, \; S \; =\) {}{}{}...
• Subtask \(4\) (\(25\%\) số điểm): \(T \; = \; 1\).
• Subtask \(5\) (\(25\%\) số điểm): \(T \; = \; 2\).