Dãy số nguyên ~A~ có ~N~ phần tử, ~A = { a_0, a_1, … a_{n-1} }~. Hai phần tử ~a_p~ và ~a_q~ gọi là thân mật nếu tổng chúng có dạng ~3^x~ với ~x \ge 1~ (ta biết rằng kí hiệu <3 thường dùng biểu thị trái tim).

Nhiệm vụ của bạn là đếm xem trong ~A~ có bao nhiêu cặp thân mật.

Input:

• Dòng 1: Số nguyên dương ~N~, giá trị không quá ~20000~.
• Dòng 2: ~N~ số nguyên là các phần tử của ~A~, các số đều không quá ~9~ chữ số (có thể có số âm).

Output:

• Số cặp thân mật đếm được

Vài test mẫu có tính tham khảo:

Sample Input 1

5
1 2 3 4 5

Sample Output 1

2

Sample Input 2

10
-3 12 -1 82 4 5 82 8 16 7

Sample Output 2

5

Dãy số ~P357(N)~ gồm các số tự nhiên có đặc tính như sau:

• Dãy được sắp tăng dần.
• Các phần tử đều nhỏ hơn ~N~.
• Ngoại trừ phần tử đầu tiên, phần tử ~A~ của dãy luôn tìm thấy ít nhất một phần tử ~B~ đứng trước nó mà (~A - 1~) chia cho ~B~ được thương số là ~3~, ~5~ hoặc ~7~.

Chú ý là có nhiều dãy thỏa mãn điều kiện trên, chẳng hạn ~P357(100)~ có thể là dãy ~\{ 1, 4, 6, 13 \}~ hoặc ~\{ 2, 7, 15, 50 \}~ hoặc rất nhiều phương án khác.

Nhiệm vụ của bạn là cần tìm dãy có tổng các phần tử lớn nhất (không nhất thiết phải là dài nhất).

Input:

• Số nguyên dương ~N~, giá trị không quá ~1~ tỉ.

Output:

• Tổng các phần tử của dãy lớn nhất.

Vài test mẫu có tính tham khảo:

Sample Input 1

10

Sample Output 1

19

Sample Input 2

100

Sample Output 2

972

Sample Input 3

1234

Sample Output 3

72557

Gọi ~A~ là mảng có ~N~ phần tử thỏa mãn ~M~ điều kiện được cho, trong đó mỗi điều kiện có dạng :

L R S

Nghĩa là tổng các phần tử liên tiếp từ vị trí ~L~ đến vị trí ~R~ trong mảng ~A~ phải bằng ~S~, nói cách khác thì ~A_L + ... + A_R = S~ ~(L \leq R)~.

Nếu tồn tại mảng ~A~ thỏa mãn tất cả ~M~ điều kiện thì hãy tìm và in ra phần tử ở vị trí thứ ~K~ của mảng ~A~. Lưu ý rằng, vị trí trong mảng ~A~ được tính từ ~1~ cho đến ~N~.

Giới hạn :

• ~1 \leq N, M \leq 200000~
• ~1 \leq K \leq N~
• ~1\leq L \leq R \leq N~ và ~-10^9 \leq S \leq 10^9~ với tất cả ~M~ điều kiện

Input :

• Dòng đầu tiền gồm ~3~ số ~N~, ~M~ và ~K~.
• ~M~ dòng tiếp theo, mỗi dòng gồm bộ ~3~ số lần lượt là ~L~, ~R~, ~S~ ứng với các điều kiện được cho.

Output :

• Nếu không tồn tại mảng ~A~ như thế thì in ra none.
• Nếu tồn tại mảng ~A~ và ~A_K~ có thể nhận nhiều giá trị khác nhau thì in ra many.
• Nếu tồn tại mảng ~A~ và ~A_K~ chỉ nhận 1 giá trị duy nhất thì in ra ~A_K~.

Test mẫu :

Sample Input 1

5 1 5
1 5 10

Sample Output 1

many

Sample Input 2

3 2 1
1 3 5
2 3 7

Sample Output 2

-2

Sample Input 3

4 3 1
1 2 5
3 4 5
1 4 11

Sample Output 3

none