Trong một tiết học đặc biệt tại phòng lab An ninh mạng của trường VH, thầy giáo tổ chức trò chơi "Cấu hình tối ưu". Thầy giáo đã thiết lập một mạng lưới giả lập gồm \(N\) nút mạng và \(M\) kết nối vô hướng. Nhiệm vụ của học sinh là tham gia lập trình điều khiển một robot ảo mang tên ClawdBot di chuyển và thu hoạch điểm trên mạng lưới này nhằm đạt được điểm số đánh giá cao nhất.

Quá trình thu hoạch điểm yêu cầu học sinh cung cấp cho hệ thống hai thông tin: (1) bản đồ cấu hình chế độ hoạt động của các nút và (2) tuyến đường di chuyển của robot. Cụ thể, học sinh cần thiết lập như sau:

1. Cấu hình mạng: Học sinh cài đặt chế độ hoạt động của \(N\) nút trên mạng lưới. Mỗi nút phải được gán một trong hai chế độ: 0 (Cực âm - Cathode) hoặc 1 (Cực dương - Anode).
2. Điều khiển ClawdBot: Học sinh chọn một nút bất kỳ làm điểm xuất phát và lập trình cho ClawdBot di chuyển liên tiếp qua tối đa \(K\) kết nối (bước đi).

Khi ClawdBot di chuyển giữa hai nút \(u\) và \(v\), hệ thống tính điểm được quy định như sau:

• Nếu \(u\) và \(v\) được cấu hình khác chế độ, ClawdBot khai thác cạnh \((u, v)\) thành công và đem lại \(B_{u,v}\) điểm thưởng.
• Nếu \(u\) và \(v\) được cấu hình cùng chế độ, hệ thống sẽ đánh dấu bước di chuyển này là bất thường và tính phạt \(P_{u,v}\) điểm.

Lưu ý: Việc kiểm tra và tính điểm thưởng/phạt này chỉ diễn ra một lần duy nhất trên mỗi cạnh. Nếu robot đi qua một kết nối từ lần thứ hai trở đi, điểm số của học sinh không bị ảnh hưởng.

Yêu cầu: Hãy tìm một phương án cấu hình cho \(N\) nút và một lộ trình di chuyển (có độ dài không quá \(K\)) cho robot ClawdBot sao cho tổng số điểm thu được là lớn nhất.

Đây là một bài output-only (chỉ nộp kết quả đầu ra). Thí sinh tải bộ dữ liệu đầu vào tại đây: ALTPATH_input-only.zip

Input

Sau khi giải nén, bạn có các file đầu vào được đặt tên là test01.inp, test02.inp, ..., mỗi file mô tả một test theo định dạng sau:

• Dòng đầu tiên chứa ba số nguyên dương \(N, M, K\) (\(2 \le N \le 1000\); \(1 \le M \le 50000\); \(1 \le K \le 10000\)).
• Mỗi dòng trong số \(M\) dòng tiếp theo chứa 4 số nguyên \(u, v, B_{u,v}, P_{u,v}\) mô tả một kết nối giữa nút \(u\) và nút \(v\), cùng với điểm thưởng \(B_{u,v}\) và điểm phạt \(P_{u,v}\) (\(1 \le u, v \le N, u \neq v; 0 \le B_{u,v}, P_{u,v} \le 10^6\)).
• Đồ thị đảm bảo không có khuyên và giữa hai nút có tối đa một kết nối.

Output

Với mỗi file đầu vào testX.inp bạn cần nộp file đầu ra testX.out tương ứng theo định dạng:

• Dòng 1: Một chuỗi nhị phân độ dài \(N\) (chỉ gồm ký tự 0 và 1). Ký tự thứ \(i\) thể hiện chế độ hoạt động của nút thứ \(i\).
• Dòng 2: Số nguyên \(L\) (\(0 \le L \le K\)) là số lượng bước di chuyển mà ClawdBot thực hiện.
• Dòng 3: \(L + 1\) số nguyên thể hiện lộ trình của ClawdBot, gồm các nút đi qua theo thứ tự. Hai nút liền kề phải có kết nối trực tiếp với nhau trong mạng lưới.

Mỗi lần nộp bài bạn có thể nộp một hoặc nhiều file đầu ra, bạn cần nén các file đầu ra này lại thành submission.zip để nộp. Ở mục chọn ngôn ngữ của trang nộp bài, chọn "Output".

Example

4 4 3
1 2 10 5
2 3 20 10
3 4 30 5
4 1 40 5

0100
3
1 2 3 4

Subtask

Ràng buộc chung: \(N \le 1000, M \le 50000, K \le 10000\).

• Subtask 1 (20 điểm): \(N \le 20, M \le 50, K \le 15\).
• Subtask 2 (30 điểm): \(P_{u,v} = 0\) với mọi \(u, v\) và dữ liệu vào đảm bảo đồ thị là hai phía.
• Subtask 3 (50 điểm): Không có ràng buộc gì thêm.

Chấm điểm

Đối với mỗi test, bạn sẽ nhận 0 điểm nếu đầu ra không hợp lệ. Một số trường hợp mà output được xem là không hợp lệ:

• Chuỗi cấu hình không có độ dài đúng bằng \(N\) hoặc chứa ký tự khác 0 và 1.
• Số lượng bước di chuyển \(L < 0\) hoặc \(L > K\).
• Lộ trình chứa nút không hợp lệ (\(< 1\) hoặc \(> N\)), hoặc hai nút liên tiếp trong lộ trình không có kết nối vật lý.

Ngược lại, gọi:

• \(C\) là tổng điểm thu hoạch phương án bạn đạt được.
• \(J\) là tổng điểm trong phương án tốt nhất mà Ban Giám Khảo biết.
• \(A\) là điểm tối đa của test. Điểm bạn nhận được trên test đó được tính bằng công thức: \(max\left(0, \left(\frac{C}{J}\right)^3\right) \cdot A\)