Bình là một nhà khảo cổ học đam mê khám phá bí ẩn về các triều đại cổ xưa. Lần này Bình phát hiện ra một bản đồ chứa thông tin về một căn hầm trong lòng đất có cất giữ bí ẩn về triều đại Chăm Pa ở khu vực Miền Trung - Tây Nguyên. Vốn là một nhà khảo cổ nhiều kinh nghiệm, để giảm thiểu tối đa rủi ro trong quá trình thám hiểm, Bình quan sát cẩn thận và giải mã những chi tiết trên bản đồ trước khi tiến vào khám phá căn hầm.

Bình phát hiện ra căn hầm được cho bởi một bảng kích thước \(N\times N\) ô vuông đơn vị. Các hàng và các cột của bảng được đánh số từ \(1\) đến \(N\). Trên bảng có \(K\) viên đá thạch anh, viên thứ \(i\) \((1\le i\le K\)) được đặt tại ô \((x_i,y_i)\), có hệ số phát sóng là \(r_i\) và phát sóng theo chu kỳ với \(r_i\) trạng thái, từ \(0\) đến \(r_i-1\), nếu một thời điểm viên đá ở trạng thái \(t\) thì thời điểm tiếp theo viên đá sẽ ở trạng thái \((t+1)\)%\(r_i\). Một viên đá ở trạng thái \(t\) sẽ phủ sóng chạm tới tất cả các ô nằm trong căn hầm có khoảng cách Manhattan nhỏ hơn hoặc bằng \(t\). Khoảng cách Manhattan giữa hai ô \((x_1,y_1)\) và ô \((x_2,y_2)\) bằng giá trị \(|x_1-x_2|+|y_1-y_2|\).

Sau một thời gian nghiên cứu, Bình tiếp tục phát hiện ra lối vào căn hầm sẽ xuống trực tiếp ô \((x_s,y_s)\) và ô lưu giữ bí ẩn về triều đại Chăm Pa là ô \((x_t,y_t)\). Bình cũng tính toán được thời điểm bước vào ô \((x_s,y_s)\) giá trị trạng thái của mỗi viên thạch anh trong căn hầm. Việc di chuyển trong căn hầm là theo từng ô, mỗi bước Bình chỉ có thể bước sang một trong bốn ô kề cạnh ngang hoặc dọc hoặc đứng yên tại ô đó. Mỗi bước tương ứng với một thời điểm chuyển trạng thái của các viên thạch anh. Nếu như Bình bước vào một ô trong tầm phủ sóng của một viên thạch anh nào đó thì cửa căn hầm sẽ tự động đóng lại và Bình sẽ gặp nguy hiểm.

Để chuẩn bị cho chuyến thám hiểm một cách an toàn nhất, Bình cần giải được hai câu hỏi sau:

1. Số lượng lớn nhất các ô bị phủ sóng tại một thời điểm bởi các viên thạch anh sau tối đa \(M\) bước là bao nhiêu?
2. Số lượng ít nhất bước để Bình di chuyển từ ô \((x_s,y_s)\) đến ô \((x_t,y_t)\) là bao nhiêu sao cho trong quá trình di chuyển Bình không đứng vào ô đang bị phủ sóng nào?

Yêu cầu: Biết được trạng thái của từng viên thạch anh, viên thứ \(i\) \((1\le i\le K)\) là trạng thái \(t_i\), tại thời điểm Bình vào hầm tại ô \((x_s,y_s)\), hãy giúp Bình trả lời hai câu hỏi trên.

Input

• Dòng đầu ghi bốn số nguyên dương \(Q\), \(N\), \(K\) và \(M\).
• Dòng thứ \(i\) trong số \(K\) dòng tiếp theo chứa \(4\) số nguyên dương \(x_i, y_i, r_i\) và \(t_i\).
• Dòng tiếp theo chứa hai số nguyên dương \(x_s\) và \(y_s\).
• Dòng cuối cùng chứa hai số nguyên dương \(x_t\) và \(y_t\).

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

Output

• Nếu \(Q=1\), ghi ra một số nguyên duy nhất là số lượng lớn nhất các ô bị phủ sóng tại một thời điểm bởi các viên thạch anh sau tối đa \(M\) bước.
• Nếu \(Q=2\), ghi ra một số nguyên duy nhất là số lượng ít nhất bước để Bình di chuyển từ ô \((x_s,y_s)\) đến ô \((x_t,y_t)\) mà không gặp nguy hiểm. Ghi ra \(-1\) nếu như không tồn tại phương án di chuyển từ ô \((x_s,y_s)\) đến ô \((x_t,y_t)\) mà Bình không gặp nguy hiểm.

Constraints

• Tại mỗi bước di chuyển, Bình không bước ra khỏi phạm vi căn hầm \(N \times N\) ô.
• Dữ liệu đảm bảo tại thời điểm bước vào căn hầm, Bình không gặp nguy hiểm, nghĩa là ô \((x_s,y_s)\) không bị phủ sóng bởi bất kỳ một viên thạch anh nào.
• Có thể có trường hợp nhiều viên thạch anh được đặt cùng một ô.
• \(Q\in \{1,2\}\).
• \(3 \le N \le 500\).
• \(1 \le K \le 15000\).
• \(1\le M \le 1000\).
• \(0 \le t_i < r_i \le 6\), \(\forall i: 1 \le i \le K\).
• \(1 \le x_s, y_s, x_f, y_f \le N\).
• \(1 \le x_i, y_i \le N\), \(\forall i: 1 \le i \le K\).

Scoring

• Subtask 1 (\(27\) điểm): \(Q=1\) và \(M=10\).
• Subtask 2 (\(23\) điểm): \(Q=1\).
• Subtask 3 (\(17\) điểm): \(Q=2\) và \(r_i=1\), \(\forall i: 1\le i\le K\).
• Subtask 4 (\(13\) điểm): \(Q=2\); \(N\le 7\) và \(r_i\le 3\), \(\forall i: 1\le i\le K\).
• Subtask 5 (\(11\) điểm): \(Q=2\); \(t_i=0\), \(\forall i: 1\le i\le K\).
• Subtask 6 (\(9\) điểm): \(Q=2\).

Examples

1 6 3 10
2 2 4 0
6 2 2 1
4 4 3 2
1 1 
6 6

26

2 7 2 3 
2 2 2 0
3 3 3 1
1 1
5 5

10