Bài tập

Bờ đê là trục hoành \(Ox\). Cuội có hai con trâu ở các điểm \((x, y)\) và \((u, v)\) trên đồng cỏ (không đổi vị trí). Cuội muốn đóng một cọc tại một điểm trên trục \(Ox\) rồi dùng hai sợi dây nối từ cọc tới từng con trâu, sao cho tổng độ dài hai sợi dây là nhỏ nhất.

Hãy in ra hoành độ của điểm đóng cọc.

Input

• Dòng đầu chứa hai số nguyên \(x\) và \(y\).
• Dòng thứ hai chứa hai số nguyên \(u\) và \(v\).

Output

In ra hoành độ của điểm đóng cọc, làm tròn đến đúng \(5\) chữ số sau dấu phẩy (dữ liệu đảm bảo không có trường hợp nằm đúng giữa hai số làm tròn).

Constraints

• \(-10^9 \le x, y, u, v \le 10^9\).
• \(y\) và \(v\) không đồng thời bằng \(0\).

Sample Input

0 3
6 1

Sample Output

4.50000

Explanation

Hai con trâu cùng phía trục \(Ox\). Lấy đối xứng \((6,1)\) qua \(Ox\) được \((6,-1)\); đường thẳng nối \((0,3)\) và \((6,-1)\) cắt \(Ox\) tại \(x = 4.5\).

Một xâu được gọi là đối xứng (palindrome) nếu đọc từ trái sang phải và từ phải sang trái đều cho cùng một dãy ký tự, chẳng hạn abba, aba, c.

Cho xâu \(S\) gồm \(N\) ký tự, đánh số từ \(1\) đến \(N\). Xâu con \(S[i..j]\) (\(1 \le i \le j \le N\)) là dãy ký tự \(S_i S_{i+1} \ldots S_j\); hai xâu con ở hai vị trí khác nhau được tính là khác nhau dù nội dung có thể giống nhau.

Có \(T\) truy vấn, mỗi truy vấn cho hai số \(a, b\) (\(a \le b\)). Với mỗi truy vấn, hãy đếm số xâu con đối xứng \(S[i..j]\) thỏa mãn \(a \le i \le j \le b\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(T\).
• Dòng thứ hai chứa xâu \(S\) độ dài \(N\), gồm các chữ cái tiếng Anh (phân biệt chữ hoa và chữ thường).
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\).

Output

• In ra \(T\) dòng, dòng thứ \(k\) là đáp án của truy vấn thứ \(k\).

Constraints

• \(1 \le N, T \le 1000\)
• \(1 \le a \le b \le N\)

Sample Input 1

5 3
abaab
1 3
2 5
4 4

Sample Output 1

4
6
1

Explanation

Với truy vấn \((1,3)\) xét xâu aba: các xâu con đối xứng là a, b, a, aba nên có \(4\) xâu.

Tại vương quốc Kimlandia, mỗi đồng vàng có ghi một số nguyên không âm. Nhà băng ở đây có luật đổi tiền rất lạ: một đồng ghi số \(n\) có thể được tách thành ba đồng mới ghi các số \(\lfloor n/2 \rfloor\), \(\lfloor n/3 \rfloor\) và \(\lfloor n/4 \rfloor\) (phép chia lấy phần nguyên). Các đồng mới lại có thể tiếp tục được tách như vậy, bao nhiêu lần tuỳ ý.

Ngoài ra, mỗi đồng vàng ghi số \(x\) có thể đổi thẳng ra \(x\) đô la với tỉ giá \(1:1\). Không thể đổi ngược từ đô la sang vàng.

Bạn đang có một đồng vàng ghi số \(n\). Hỏi số đô la nhiều nhất có thể thu được là bao nhiêu?

Input

Dữ liệu gồm nhiều bộ test (không quá \(10\)), mỗi bộ test là một dòng chứa một số nguyên \(n\). Dữ liệu kết thúc ở cuối tệp.

Output

Với mỗi bộ test in ra một dòng là số đô la lớn nhất thu được.

Constraints

• \(0 \le n \le 10^9\)

Sample Input

6
11
13
24
100
999
987654321

Sample Output

6
11
13
27
120
1370
4241507870

Explanation

Với \(n = 13\): tách thành \(6, 4, 3\) chỉ được \(13\), bằng đổi thẳng. Với \(n = 24\): tách thành \(12, 8, 6\); đồng \(12\) lại tách thành \(6, 4, 3\) (tổng \(13\)), cộng \(8 + 6\) được \(27\).

Tại hội đêm rằm, Nam có \(X\) điểm thưởng để đổi quà. Có \(N\) món quà, món thứ \(i\) có giá \(A_i\) điểm. Nam muốn đổi đúng hai món quà khác nhau (hai món ở hai vị trí khác nhau trong danh sách) sao cho tổng giá trị lớn nhất có thể nhưng không vượt quá \(X\).

In ra tổng giá trị đó. Nếu không có cặp nào có tổng không quá \(X\) (kể cả khi \(N = 1\)) thì in ra \(0\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(X\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

Một số nguyên là tổng giá trị lớn nhất không vượt quá \(X\) của hai món quà khác nhau, hoặc \(0\) nếu không thể.

Constraints

• \(1 \le N \le 100001\)
• \(1 \le X \le 10^9\)
• \(1 \le A_i \le 10^9\)

Sample Input

7 18
6 11 3 9 14 5 2

Sample Output

17

Explanation

Các cặp tốt nhất là \(14 + 3 = 17\) hoặc \(11 + 6 = 17\); không có cặp nào có tổng bằng \(18\).