Với số nguyên dương ~n~. Em hãy tính tổng ~S~, với công thức tính S như sau:

• ~S = 1 + 3 + 5 + … + n~, nếu ~n~ lẻ.

• ~S = 2 + 4 + 6 + … + n~, nếu ~n~ chẵn.

Input

Một dòng duy nhất là só nguyên ~n~ ~(1 \le n \le 10^9)~

Output

In ra tổng ~S~ vừa tìm

Sample Input

5

Sample Output

9

Subtask

• Có ~60\%~ test với ~1 \le n \le 10^6~.

• Có ~40\%~ test với ~10^6 < n \le 10^9~.

Một số nguyên dương được gọi là số ~\text{Niven}~ (hoặc số ~\text{Harshad}~) nếu nó chia hết cho tổng các chữ số của nó.

Một số được gọi là số ~\text{Niven}~ cân bằng nếu số đó là số ~\text{Niven}~ và có số lượng chữ số chẵn bằng số lượng chữ số lẻ.

Ví dụ: ~10, 12, 45~ là các số ~\text{Niven}~ cân bằng, còn ~14, 25, 28~ không là các số ~\text{Niven}~ cân bằng.

Yêu cầu: Cho một số nguyên dương ~n~, em hãy tìm số ~\text{Niven}~ cân bằng lớn nhất nhỏ hơn hoặc bằng ~n~.

Input

Gồm một số nguyên dương ~n~ ~(10 \le n \le 10^6)~.

Output

Một số nguyên là đáp án của bài toán.

Sample Input 1

1212

Sample Output 1

1212

Giải thích

Giải thích: test 1, với ta có số ~1212~ là số ~\text{Niven}~ cân bằng lớn nhất nhỏ hơn hoặc bằng ~n~ vì số ~1212~ có số lẻ và ~2~ chữ số chẵn, đồng thời tổng các chữ số là ~6~ nên ~1212~ chia hết cho ~6~.

An và Bình chơi với nhau rất thân. Hai bạn thường chơi đố vui trong những giờ rảnh rỗi. Một lần, An cho Bình một bài toán như sau:

"Cho một dãy số nguyên ~A~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~. Ban đầu tất cả các phần tử của dãy đều có giá trị là ~0~. Thực hiện ~Q~ lần thay đổi giá trị các phần tử của dãy. Lần thứ ~i~ trong ~Q~ lần đó, thực hiện thay đổi từ phần tử thứ ~u~ đến phần tử thứ ~v~ một lượng là ~M~, nghĩa là nếu ~M~ âm thì mỗi phần tử trong đoạn ~[u, v]~ sẽ giảm đi ~M~, còn ~M~ dương thì tăng mỗi phần tử đó lên ~M~. Sau ~Q~ lần thực hiện thay đổi như thế, hãy cho biết số lớn nhất trong dãy là bao nhiêu?"

Em hãy giúp Bình tìm ra đáp án của bài toán nhé!

Input

Dòng thứ nhất chứa hai số nguyên ~n~ và ~Q~, giữa hai số cách nhau một khoảng trắng ~(1 \le n, Q \le 10^6)~.

Dòng thứ hai đến dòng ~Q+1~, mỗi dòng gồm ba số nguyên ~u, v, M~, giữa hai số cách nhau một khoảng trắng ~(1 \le u \le v \le n và M ≠ 0, |M| ≤ 10^6)~.

Output

In ra số lớn nhất tìm được.

Sample Input

4 3
1 2 3
2 4 -1
3 4 7

Sample Output

6

Subtask

Có ~70\%~ test có ~1 \le n, Q \le 10^3~.

Có ~30\%~ test có ~10^3 < n, Q \le 10^6~.

Giải thích

Với ~n = 4, Q = 3~, dãy ban đầu: ~0 0 0 0~

Sau lần biến đổi thứ nhất: ~3 3 0 0~

Sau lần biến đổi thứ hai: ~3~ ~2~ ~-1~ ~-1~

Sau lần biến đổi thứ ba: ~3~ ~2~ ~6~ ~6~

Kết quả: Giá trị lớn nhất của dãy là ~6~.

Cho một xâu ~S~ gồm một hay nhiều từ tiếng Anh, mỗi từ gồm các chữ cái in thường từ ~a~ đến ~z~ liên tiếp nhau. Giữa hai từ cách nhau bởi một hay nhiều khoảng trắng. Em hãy tìm trong xâu ~S~ xem từ nào có độ đa dạng cao nhất. Biết rằng độ đa dạng một từ là số ký tự khác nhau có trong từ đó.

Input

Dòng duy nhất gồm một xâu ~S~ khác rỗng có độ dài xâu không quá ~10^6~.

Output

Một từ có độ đa dạng cao nhất, nếu có nhiều từ thỏa mãn thì ghi ra từ có vị trí nhỏ nhất trong xâu S thỏa mãn yêu cầu bài toán.

Sample Input

book teacher banana lesson future cooking
red green blue

Sample Output

teacher
green

Subtask

Có ~50\%~ test có độ dài xâu ~S~ không quá ~10^3~ và không có khoảng trắng nào ở đầu xâu, cuối xâu, đồng thời giữa các từ có một khoảng trắng.

Có ~50\%~ test còn lại có giới hạn như trong đề.

Số nguyên tố là số nguyên dương lớn hơn ~1~ và chỉ có hai ước dương là ~1~ và chính nó.

Ví dụ: ~2, 3, 7, 13~ là các số nguyên tố còn ~4, 6, 20~ không là số nguyên tố.

Khôi đang học về số nguyên tố. Hôm nay, thầy giáo cho một dãy số nguyên dương ~A~ gồm ~n~ phần tử ~A_1, A_2, …, A_n~ và yêu cầu Khôi đếm số lượt đổi chỗ ít nhất các phần tử của dãy ~A~ để tất cả các số nguyên tố trong dãy được gom vào một miền liên tiếp.

Em hãy giúp Khôi tìm ra đáp án của bài toán nhé!

Input

Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.

Dòng tiếp theo chứa n số nguyên dương ~A_1, A_2, …, A_n~, giữa hai số cách nhau một khoảng trắng ~(1 \le A_i \le 10^9)~.

Output

Một số nguyên dương duy nhất là số lượng đổi chỗ ít nhất để được miền nguyên tố lớn nhất.

Sample Input

7
10 2 3 6 78 5

Sample Output

1

Giải thích

Đổi chỗ số ~6~ và số ~5~ để các số nguyên tố được gom vào một miền duy nhất.

Subtask

• Có ~50\%~ test có ~n \le 10^3, A_i \le 10^3~.

• Có ~30\%~ test có ~n \le 10^4, Ai \le 10^5~.

• Có ~20\%~ test có giới hạn như trong đề.