Số học luôn là một lĩnh vực quyến rũ với các định lý đẹp, và đôi khi cũng nguy hiểm chết người. Có những tính chất ta nghĩ là dễ nhưng biến đổi thử mới thấy khó, nhưng đôi khi ngược lại, có những kết quả khá hiển nhiên mà ta thường tìm tòi những thứ rất xa xôi.

Do biết team ICPC của H3.2 cũng rất thích số học, đặc biệt là những bài đố mẹo, đố vui nên hôm nay, thầy Luna có giới thiệu một bài như sau: cho số nguyên dương ~n, m~, hỏi số ~n^{m!}~ thì chia cho ~2024~ dư mấy? Bạn hãy thử sức với bài toán đố vui này nhé.

Input

Một dòng duy nhất gồm hai số nguyên dương ~n, m~ với ~1 \le n, m \le 10^{18}~.

Output

Kết quả của bài toán.

Sample input 1

3 2

Sample output 1

9

Sample input 2

2023 100000

Sample output 2

1

Subtasks

• Có 25% test ứng với ~n, m \le 15~.
• Có 25% test ứng với ~m \le 15~.
• Có 50% test với giới hạn tùy ý.

Sau những ngày chinh chiến với CP, anh Phú về quê nghỉ dưỡng một thời gian và trồng hoa cùng chị. Vườn hoa của anh Phú có kích thước ~m \times n~ và trồng nhiều loại hoa có chiều cao nhất định. Nhưng vì vườn hơi rộng nên chị muốn chọn ra một phần trong vườn có kích thước ~h \times w~ để chăm sóc cho dễ, kịp đón Tết. Để phần vườn đó đẹp nhất, các cây hoa phải có chiều cao bằng nhau và Phú cần phải chọn ra một giá trị chiều cao ~x~ nào đó rồi thực hiện các thao tác: nếu trong phần vườn đang chọn, có hoa cao hơn ~x~ thì Phú sẽ đào đất sâu hơn để trồng cho hoa thấp vừa bằng ~x~; còn nếu hoa thấp hơn ~x~ thì Phú lại đắp đất cao hơn để hoa cao vừa bằng ~x~. Mỗi đơn vị chênh lệch chiều cao sẽ tốn của Phú thời gian không nhỏ, vì thế nên bạn sẽ chọn ra giá trị ~x~ để tiết kiệm công sức nhất có thể.

Biết Phú vất vả nên chị cũng muốn tính toán xem trong các cách chọn vị trí phần vườn thì giá trị ~x~ tương ứng có thể nhỏ nhất là bao nhiêu. Bạn hãy giúp chị trả lời câu hỏi này nhé.

Input

Dòng đầu tiên gồm 4 số nguyên ~m, n, h, w~ cho biết kích thước liên quan, trong đó ~1 \le h \le m \le 10^3~ và ~1 \le w \le n \le 10^3.~

Trong các dòng tiếp theo, ta có thông tin về chiều cao các bông hoa trong vườn chị, giá trị nguyên không âm và không vượt quá ~10^9.~

Output

Đáp số của bài toán.

Sample input

5 6 3 3
89 53 45 1 1 76
76 77 66 73 76 53
1 71 91 17 55 61
91 19 9 29 21 89
11 21 81 81 61 81

Sample output

21

Giải thích: ta có thể chỉ ra được nếu chọn phần vườn ~3 \times 3~ ở góc dưới bên trái thì giá trị ~x~ Phú sẽ chọn là ~21~, và chứng minh được số này là nhỏ nhất có thể.

Subtasks

• Có 20% số test có ~m, n ≤ 30~
• Có 20% số test có ~m, n ≤ 100~
• Có 30% số test có ~m, n≤ 300;~
• Có 30% số test có giới hạn như dữ kiện bài ra.

Lộc và Tài tuy ở chung phòng nhưng hay gửi thư cho nhau. Mỗi bức thư chỉ có viết 1 từ duy nhất viết bằng các chữ cái tiếng Anh in thường, nhưng có độ dài rất lớn. Thực ra mỗi từ đó có chứa một thông điệp ẩn giấu mà phải người trong cuộc mới có thể tìm ra được: thông điệp là một xâu đối xứng dài nhất có thể có trong bức thư, được tạo thành từ việc xóa đi một số ký tự gây nhiễu liên tiếp nào đó (bản chất là ghép một phần đầu và một phần cuối của bức thư lại với nhau).

Bạn cùng phòng của Lộc và Tài vừa tìm ra được danh sách ~n~ bức thư của họ, họ cũng nghe trộm được cách truyền tải thông điệp giữa hai bạn nên muốn ngồi giải mã ra từng thông điệp đó xem có gì hot không. Hỏi độ dài của các thông điệp tìm được là bao nhiêu?

Input

Dòng đầu tiên gồm số nguyên dương ~t~ với ~1 \le t \le 10^5~ là số bức thư. Trong ~t~ dòng tiếp theo, mỗi dòng là một từ duy nhất.

Output

Với mỗi bức thư, cho biết độ dài của thông điệp tìm được.

Sample input

5
a
abcdfdcecba
abbaxyzyx
codeisfun
acbba

Sample output

1
9
5
1
4

Giải thích Trong bức thư thứ hai, thông điệp cần tìm là ~abcdfdcba~, còn trong bức thư thứ ba, thông điệp cần tìm là ~xyzyx~.

Subtasks

Gọi M là tổng độ dài tất cả các xâu ~S~ trong mỗi test.

• Subtask 1 (50%): ~t≤1000,M≤5000~
• Subtask 2 (50%): ~t≤10^5,M≤10^6.~

IUHCoder là một công ty khởi nghiệp còn nhiều vấn đề về nhân sự cần giải quyết. Hiện tại, công ty đang có n nhân viên. Sơ đồ mối quan hệ của các nhân viên là đồ thị cây n-1 mối quan hệ thân thiết. Biết rằng chủ tịch Hội đồng quản trị Tina đang cần tìm một giám đốc cho công ty để tăng hiệu quả quản trị. Gọi thời gian truyền tin là tổng thời gian truyền tải thông tin từ giám đốc đến tất cả nhân viên còn lại, hai nhân viên có mối quan hệ thân thiết với nhau sẽ mất 1 đơn vị thời gian để truyền tải thông tin cho nhau. Rõ ràng là thời gian truyền tin cảng nhỏ thì hiệu quả càng cao.

Hiện tại vị trí giám đốc đang do nhân viên thứ 1 trong công ty đảm nhận. Sếp Tina có thể chuyển vị trí giám đốc cho một nhân viên có quan hệ thân thiết với giám đốc hiện tại (ban đầu là nhân viên 1) và mất c đơn vị thời gian để quyết định chọn hay không, đồng thời hiệu thời gian truyền tin cũng có thể tăng học giảm tuy vào chất lượng mỗi quan hệ của nhân viên đó. Vì công ty IUHCoder đang ngày một phát triển, số lượng người làm trong công ty quá lớn và Tina đang có rất nhiều công việc cũng quan trọng không kém. Bạn là một nhân viên xuất sắc trong công ty, hãy tính tổng thời gian Tina chọn đựọc một nhân viên làm giám đốc và thời gian truyền tin đến tất cả các nhân viên còn lại là ít nhất.

Input

Dòng đầu tiên gồm 2 số n và (~ 2 \le n \le 2.10^5, 1 \le c \le 10^2 ~) - số nhân viên của công ty và thời gian để quyết định chọn một nhân viên làm giám đốc hay không.

Tiếp theo n-1 dòng gồm 2 số u và v (~ 1 \le u, v \le n ~) - hai nhân viên thứ u và v có mối quan hệ thân thiết với nhau.

Subtask 1: (40% số điểm) ~ 1 \le n \le 2.10^3 ~

Subtask 2: (15% số điểm) ~ 1 \le n \le 2.10^5 ~, với mối quan hệ thứ i (~1 \le i \le n-1~) thõa u = i, v = i + 1

Subtask 3: (45% số điểm) Không có ràng buộc gì thêm.

Output

Một dòng duy nhất là tổng thời gian Tina chọn đựọc một nhân viên làm giám đốc và thời gian truyền tin đến tất cả các nhân viên còn lại là ít nhất.

Examples

Input

6 2
1 2
2 4
4 5
4 6
2 3 

Output

9

*Giải thích: * Phương án tối ưu nhất là chọn nhân viên thứ 2 làm giám đốc, mất 2 đơn vị thời gian để Tina quyết định và 1 + 0 + 1 + 1 + 2 + 2 để truyền tin cho các nhân viên còn lại. Tổng thời gian cần thiết là 9.