Trong luật cờ vua, mỗi nước đi của quân mã được quy định như sau: quân mã đang ở vị trí X như hình vẽ bên dưới có thể di chuyển đến một trong các ô mà mũi tên chỉ đến (theo đường chéo của hình chữ nhật ~2 \times 3~)

Cho trước bàn cờ kích thước ~N \times M~ ô. Hãy đếm số nước đi ít nhất để quân mã di chuyển từ ô có tọa độ ~(x_1, y_1)~ đến ô có tọa độ ~(x_2, y_2)~. Trong trường hợp không đến được thì ghi ra giá trị ~-1~.

Input

Cho từ tệp văn bản QUANMA.INP gồm:

• Dòng 1 ghi 2 số nguyên dương ~N~, ~M~ ~(2≤ N, M ≤1000)~.

• Dòng 2 ghi 2 số nguyên ~x_1~, ~y_1~ ~(1≤x_1≤N~; ~1≤y_1≤M)~

• Dòng 3 ghi 2 số nguyên ~x_2~, ~y_2~ ~(1≤x_2≤N~; ~1≤y_2≤M)~

Các số trên cùng một dòng cách nhau ít nhất một ký tự trắng.

Output

Ghi ra tệp văn bản QUANMA.OUT một số nguyên duy nhất cho biết số nước đi ít nhất để quân mã di chuyển từ ô ~(x_1, y_1)~ đến ô ~(x_2, y_2)~. Nếu quân mã không đến được thì ghi số ~-1~.

Sample Input 1

4 6
1 1
2 4

Sample Output 1

2

Một hệ thống giao thông gồm ~n~ thành phố được đánh số từ ~1~ đến ~n~. Hệ thống giao thông có ~m~ đoạn đường hai chiều nối giữa các thành phố (giữa hai thành phố bất kỳ luôn có đường đi). Mỗi đoạn đường có một tải trọng tối đa là ~z~, cho biết các xe với tải trọng không lớn hơn ~z~ mới lưu thông được trên con đường đó.

Yêu cầu: Cho trước tải trọng của các đoạn đường trong hệ thống giao thông. Hãy tìm một hành trình từ thành phố ~s~ đến thành phố ~t~ sao cho tải trọng cho phép của xe lưu thông trên hành trình đó là lớn nhất có thể.

Input

Cho từ tệp văn bản TAITRONG.INP gồm:

• Dòng thứ nhất ghi ~4~ số nguyên ~n,\ m,\ s,\ t~ ~(2\le n \le 10^3;\ 1\le m \le 10^4;\ 1\le s,\ t\le n; s\ne t)~.

• Tiếp theo là ~m~ dòng, mỗi dòng ghi ~3~ số nguyên ~x,\ y,\ z~ với ý nghĩa có đoạn đường giữa thành phố ~x~ và thành phố ~y~ với tải trọng tối đa cho phép là ~z~ ~(1 \le z \le 10^4)~.

  Các số trên cùng dòng viết cách nhau bởi ít nhất một dấu cách.

Output

Ghi vào tệp văn bản TAITRONG.OUT gồm một dòng ghi số nguyên là tải trọng lớn nhất cần tìm.

Scoring

~50\%~ số test tương ứng với ~50\%~ số điểm của bài có ~2\le n \le 100~.

Sample Input 1

4 5 1 4
1 2 10
2 4 1
1 3 5
3 4 3
1 4 2

Sample Output 1

3

Chùa Hương là một quần thể di tích thuộc địa phận xã Hương Sơn, huyện Mỹ Đức, thành phố Hà Nội. Chùa Hương gồm nhiều chùa chiền (đáng chú ý nhất là chùa Thiên Trù) cùng với động Hương Tích rất nổi tiếng (được mệnh danh là Nam thiên đệ nhất động)

Vào mùa lễ hội (tháng Giếng đến tháng Ba âm lịch hàng năm), chú tiểu Bờm phải làm việc khá vất vả. Hằng ngày, Bờm phải từ chùa Thiên Trù xuống lưng chừng núi Lão rồi từ đố leo tiếp lên gần đỉnh nói đến động Hương Tích. Sau đó, từ động Hương Tích, Bờm quay lại chùa Thiên Trù theo con đường ban đầu. Con đường bao gồm ~2~ đoạn dãy bậc thang lát đá với số bạc lần lượt là ~M~ và ~N~ (xem hình minh họa). Hành trình của Bờm như sau:

• Từ chùa Thiên Trù đi xuống lưng chừng núi Lão cũng như từ đây đi lên động Hương Tích, vì đi người không nên Bờm có thể bước qua ~1~, ~2~ hoặc ~3~ bậc tùy thích.
• Khi đi từ động Hương Tích xuống lưng chừng núi Lão, di phải gánh đồ nên Bờm chỉ có thể bước qua ~1~ hoặc ~2~ bậc đồng thời sử dụng đúng ~1~ lần bước qua ~3~ bậc tại vị trí tùy thích. Tuy nhiên, khi leo tiếp lên chùa Thiên Trù, Bờm chỉ có thể bước qua ~1~ hoặc ~2~ bậc mà thôi.

Yêu cầu: Hãy tính xem có thể có bao nhiêu cách để Bờm thực hiện một chuyến đi-về trong một ngày như vậy.

Input

Từ tệp văn bản CHUTIEU.INP gồm nhiều dòng, mỗi dòng là một cặp giá trị của ~M~ và ~N~ ~(3\le M,\ N \le 500)~.

Các số ghi trên cùng một dòng ghi cách nhau ít nhất là một ký tự trắng.

Output

Ghi ra tệp văn bản CHUTIEU.OUT gồm nhiều dòng, mỗi dòng là kết quả tìm được ứng với cặp giá trị của ~M,\ N~ thuộc dòng tương ứng tệp dữ liệu vào.

Scoring

~50\%~ số test ứng với ~50\%~ số điểm của bài có ~M\le 20,\ N\le 20~.

Sample Input 1

3 4
4 5
10 15
22 19

Sample Output 1

168
2275
321404553680
15760806775373345664