Trong phòng thí nghiệm chỉ có đúng ba loại cốc có dung tích là \(5 \ (ml)\), \(3 \ (ml)\) và \(2 \ (ml)\). Hỏi cần ít nhất bao nhiêu lần đong nước để lấy được đúng \(N \ (ml)\).

Input:

Một số nguyên dương duy nhất \(N\) \((2 \le N \le 10^{18})\) là số nước cần đong.

Output:

Một số nguyên dương duy nhất là số lượng lần đong ít nhất thoả mãn yêu cầu đề bài.

Ví dụ

Input

12

Output

3

Giải thích

Đong hai lần bằng cốc \(5 \ (ml)\) và một lần bằng cốc \(2 \ (ml)\).

Input

6

Output

2

Giải thích

Đong hai lần bằng cốc \(3 \ (ml)\).

Trong phòng thí nghiệm, các nhà khoa học đang nghiên cứu về gen của một chuỗi ARN đặc biệt được mã hoá bằng một xâu \(S\) gồm các kí tự A, U, G, X).Họ muốn cắt từ chuỗi ARN đó một mạch (được mã hoá bằng xâu \( X \) ) cho trước.

Yêu cầu: từ chuỗi ARN có thể cắt được ra tối đa bao nhiêu đoạn mạch \( X \) .

Input

• Dòng đầu tiên gồm một xâu kí tự \(S\) mô tả chuỗi ARN;
• Dòng thứ hai gồm một xâu kí tự \( X \) mô tả đoạn mạch cần cắt ra.
  Các xâu chỉ gồm các kí tự A, U, G, X và độ dài các xâu không quá \( 10^3 \) kí tự.

Output

• Một số nguyên duy nhất: số lần tối đa có thể cắt đoạn mạch \( X \).

Example

AUAUGXXAUGXGX
AUGX 

2

AAAAA
AAA

1

AGAX
U

0

Cho một dãy số gồm \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) có giá trị không vượt quá \(10^6\). Tìm dãy con liên tiếp ngắn nhất có chứa ít nhất hai số nguyên tố.

Input:

• Dòng đầu tiên gồm một số nguyên dương \(N \ (N \le 10^6)\) là số lượng phần tử của dãy số;
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) lần lượt mô tả các phần tử của dãy số.

Output:

Một số nguyên duy nhất là số lượng phần tử của dãy con thoả mãn đề bài. Trường hợp không tồn tại dãy con thoả mãn, in ra \(-1\).

Ví dụ

Input

10
3 4 8 4 5 6 1 7 4 6

Output

4

Giải thích

Chọn dãy con từ vị trí thứ \(5\) đến vị trí thứ \(8\): \(5, 6, 1, 7\).

Ràng buộc

• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài thoả mãn: \(N \le 10^3; \ a_i \le 10^3\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(N \le 10^6; \ a_i \le 10^3\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.

Chuẩn bị Gala mừng năm mới Tết Tân Sửu 2021 của công ty HiTech, ban giám đốc quyết định có giải thưởng đặc biệt cho thành viên của công ty. Sau khi đưa ra các tiêu chí đánh giá, việc bầu chọn sẽ được thực hiện bằng cách tất cả các thành viên sẽ được bỏ phiếu cho nhau.
Hình thức bỏ phiếu được thực hiện thông qua phiếu bầu chọn online. Danh sách các thành viên của công ty được niêm yết và quy định là số thứ tự từ \(1\) đến \(N (1\le N\le 5000)\), tương ứng với \(N\) ô trên phiếu bầu chọn. Sau khi thực hiện, ban tổ chức thu được các danh sách phiếu tương ứng của các thành viên công ty. Trong mỗi phiếu bầu chọn, giá trị ô ở vị trí tương ứng ghi "X" là bầu chọn cho người đó, ô ghi "0" là không bầu chọn (coi các trường hợp bầu chọn không hợp lệ là không bầu chọn).

Yêu cầu: Em hãy giúp ban tổ chức đưa ra danh sách các nhân viên có phiếu bầu chọn cao nhất.

Input

• Dòng đầu tiên gồm số một số nguyên dương \(N (1\le N\le 5000)\) là số lượng phiếu bầu chọn.
• \(N\) dòng tiếp theo mỗi dòng tương ứng là \(N\) giá trị của các phiếu đã bầu chọn.

Output

• Dòng đầu tiên ghi số lượng người được nhiều phiếu nhất và số lượng phiếu.
• Dòng thứ hai ghi thứ tự tương ứng của những người được cao phiếu nhất đó theo thứ tự tăng dần.

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(N\le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(N\le 5000\).

Example

5
X 0 X 0 X
X 0 0 X X
0 0 X 0 0
0 X 0 X 0
0 0 X X 0

2 3
3 4

Trong một trò chơi, có \(N\) người chơi xếp thành một vòng tròn và được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Trước khi trò chơi bắt đầu, sẽ có \(M\) lượt phát đồng xu cho người chơi với nguyên tắc như sau:

• Mỗi lượt, chọn ngẫu nhiên hai số nguyên dương \(L\) và \(R\) \((L \le R)\), phát một đồng xu cho tất cả những người chơi từ số \(L\) đến số \(R\) theo chiều kim đồng hồ.

Yêu cầu: Cho trước \(N\), \(M\) và các cặp \(L\), \(R\). Tìm:

• Số đồng xu lớn nhất mà một người chơi được phát.
• Số người chơi nhận được số đồng xu lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) \((1 \le M \le 10^5)\).
• \(M\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(L\) và \(R\) \((1 \le L, R \le N)\).

Output

• Gồm hai số nguyên:
• Số đồng xu lớn nhất mà một người chơi được phát.
• Số người chơi đạt được số đồng xu đó.

Subtasks

• 60% số test: \(N, M \le 10^3\)
• 20% số test: \(N \le 10^5\)
• 20% số test: \(N \le 10^9\), \(M \le 10^5\)

Sample Test

5 2
1 5
4 2

2 4

Giải thích

• Số đồng xu của mỗi người theo thứ tự:
• Ban đầu: 0 0 0 0 0
• Lượt 1 (1 → 5): 1 1 1 1 1
• Lượt 2 (4 → 2): 2 2 1 2 2
  => Người có nhiều đồng nhất: 2 đồng xu. Số người có 2 đồng xu: 4.

Cho một hình chữ nhật gồm \( N \) dòng và \( M \) cột. Các dòng được đánh số từ 1 đến \( N \) , từ trên xuống dưới. Các cột được đánh số từ 1 đến \( M \) , từ trái sang phải. Ô ở dòng thứ \( i \) và cột thứ \( j \) được gọi là ô (\( i, j \)) và có diện tích là 1 đơn vị. Có một số ô đã được điền sẵn kí tự \( 'X' \).

Yêu cầu: tìm hình chữ nhật con có diện tích lớn nhất chỉ chứa duy nhất một kí tự \( 'X' \).

Input

• Dòng đầu tiên gồm ba số nguyên dương \( N, M, K \)(\( N, M ≤ 10^4, K ≤ 10^3 \)) mô tả kích thước của hình chữ nhật và số lượng kí tự \( ′X′ \) có trong hình chữ nhật;
• \(K\) dòng sau, mỗi dòng gồm hai số nguyên dương \( d \) và \( c \) là chỉ số dòng và cột của ô điền kí tự \( ′X′ \) (\( d ≤ N; c ≤ M\)).

Output

• Ghi ra diện tích của hình chữ nhật lớn nhất thoả mãn yêu cầu đề bài..

Scoring

• Có 50% số test tương ứng với 50% số điểm thoả mãn: \( N, M ≤ 50 \) ;
• 30% số test khác tương ứng với 30% số điểm thoả mãn: \( N, M ≤ 500 \);
• 20% số test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.

Example

4 5 4
2 3
2 5
3 1
4 4

9