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, ..., 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á bài 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

• Lần thứ hai An sẽ chia các lá bài:

  2

  5

  8

  11

  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.

Dữ liệu đầu vào

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

Dữ liệu đầu ra

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

Ràng buộc dữ liệu

• Có 50% số test với ~n \le 1000~.
• 50% số test còn lại không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

INPUT

15

OUTPUT

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.

Ví dụ với bản đồ dưới đây, ta có ~4~ đảo.

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ể.

Dữ liệu đầu vào

Gồm ~m + 1~ dòng:

• 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 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~.

Dữ liệu đầu ra

Gồm 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 ô.

Ràng buộc dữ liệu

• Có 20% số test với bảng chỉ có đúng một hòn đảo;
• Có 40% số test khác với ~m, n \le 50~;
• 40% số test còn lại không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

INPUT

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

OUTPUT

14

Giải thích: Có thể chọn lắp ô ~(4, 3)~ nhận bản đồ:

1 0 1 0 1 1

1 0 1 0 1 1

1 1 1 0 0 0

0 0 1 1 1 1

1 1 0 0 1 0

1 1 1 0 1 1

Trên bản đồ có đảo gồm ~14~ ô.

Nam vừa mua một chiếc Iphone 15 và cần cài đặt mật khẩu cho chiếc điện thoại thông minh này. Mật khẩu gồm ~4~ chữ số. Việc lựa chọn trước đây thường là năm sinh của chính mình hay của người thân. Lần này Nam nghĩ ra một cách chọn độc đáo mật khẩu cho chiếc Iphone mới này.

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...~ Dãy chữ số khi viết tới số ~24~ là:

~a = 123456789101112131415161718192021222324\ldots~

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.

Dữ liệu đầu vào

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

Dữ liệu đầu ra

Gồm 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.

Ràng buộc dữ liệu

• Có 50% số test với ~k \le 10^6~;
• Có 50% số test còn lại không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

INPUT

21

OUTPUT

5161