Trên bàn có một dãy các ô, các ô đánh số liên tiếp bắt đầu từ ~1~, từ trái sang phải. An có một bộ bài gồm ~n~ lá bài có số hiệu là ~1, 2, 3, \dots, n~. Để chọn ra lá bài may mắn bạn An thực hiện các thao tác như sau:

Bước 1: An chia các lá bài hiện có vào các ô liên tiếp bắt đầu từ ô thứ nhất với số hiệu các lá bài theo thứ tự tăng dần.

Bước 2: An nhặt các lá bài trong các ô có số thứ tự chia cho ~3~ dư ~2~ và loại bỏ các lá bài còn lại trên dãy. Nếu số lá bài nhặt được nhiều hơn ~1~ thì quay lại thực hiện Bước 1. Trong trường hợp nhặt được đúng ~1~ lá thì lá bài đó là lá bài may mắn.

Ví dụ: Với ~n = 15~:

• Lần thứ nhất An sẽ chia các lá bài: ~1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15~ Nhặt các lá bài ~2, 5, 8, 11, 14~.
• Lần thứ hai An sẽ chia các lá bài: ~2, 5, 8, 11, 14~ Nhặt các lá bài ~5, 14~.
• Lần thứ ba An sẽ chia các lá bài: ~5, 14~ Nhặt lá bài ~14~ là lá bài may mắn.

Yêu cầu: Cho biết ~n~, hãy tìm ra số hiệu của lá bài may mắn.

Input

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

Output

• Ghi ra một số nguyên dương duy nhất là số hiệu của lá bài may mắn.

Sample Input 1

15

Sample Output 1

14

Bản đồ một vùng đất là một hình chữ nhật kích thước ~m \times n~ được chia làm lưới ô vuông đơn vị, các hàng của lưới được đánh số từ ~1~ tới ~m~ từ trên xuống dưới và các cột của lưới được đánh số từ ~1~ tới ~n~ từ trái qua phải. Ô nằm trên giao của hàng ~x~, cột ~y~ được gọi là ô ~(x, y)~, mỗi ô có hai trạng thái là ô nước hay ô đất. Bản đồ được mô tả bởi bảng ~h(m \times n)~ với ~h_{xy} = 1~ nếu ô ~(x, y)~ là đất và ~h_{xy} = 0~ nếu ô ~(x, y)~ là nước.

Những ô đất tạo thành những "đảo" định nghĩa như sau: Hai ô đất gọi là cùng đảo nếu ta có thể đi từ ô này tới ô kia bằng cách di chuyển qua các ô kề cạnh là đất, ngược lại hai ô đó được coi là nằm trên hai đảo khác nhau.

Yêu cầu: Bạn được phép lấp đúng ~1~ ô nước để trở thành ô đất (tức là đổi giá trị một ô ~0~ thành ~1~) sao cho sau khi lấp thì nhận được một đảo có diện tích lớn nhất có thể.

Input

• Dòng ~1~ chứa hai số nguyên dương ~m, n \le 1000~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số, số thứ ~j~ là ~h_{ij} = 0~ hoặc ~1~. Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách. Dữ liệu đảm bảo trên bản đồ có ít nhất một ô bằng ~0~.

Output

• Ghi ra một số nguyên duy nhất là số ô của đảo lớn nhất nhận được sau khi lấp một ô.

Sample Input 1

6 6
1 0 1 0 1 1
1 0 1 0 1 1
1 1 1 0 0 0
0 0 0 1 1 1
1 1 0 0 1 0
1 1 1 0 1 1

Sample Output 1

14

Nam viết liên tiếp các số nguyên dương bắt đầu từ ~1~ thành một dãy các chữ số vô hạn và đánh số các chữ số này bắt đầu từ ~1~ tạo thành dãy số ~a = a_1a_2a_3 \dots~. Dãy chữ số khi viết tới số ~24~ là: ~a = 123456789101112131415161718192021222324 \dots~

Như vậy chữ số thứ ~20~ là ~1~ (~a_{20} = 1~), chữ số thứ ~21~ là ~5~ (~a_{21} = 5~).

Nam chọn một số nguyên dương ~k~ và ~4~ chữ số liên tiếp bắt đầu từ chữ số thứ ~k~: ~a_k a_{k+1} a_{k+2} a_{k+3}~ là mật khẩu chiếc Iphone của Nam.

Yêu cầu: Cho số ~k~, hãy tìm ~4~ chữ số ~a_k a_{k+1} a_{k+2} a_{k+3}~ là mật khẩu chiếc Iphone của Nam.

Input

• Gồm duy nhất một số nguyên dương ~k \le 10^{14}~.

Output

• Ghi một dòng ghi liên tiếp ~4~ chữ số ~a_k a_{k+1} a_{k+2} a_{k+3}~ tìm được.

Sample Input 1

21

Sample Output 1

5161