Cho một cây gồm \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\). Đỉnh \(1\) là gốc của cây. Với các đỉnh còn lại, đỉnh thứ \(i\) có cha là đỉnh \(p_{i}\). Mỗi đỉnh trên cây có ba loại giá trị; các loại giá trị này của đỉnh thứ \(i\) được ký hiệu là \(w_{i}, b_{i}\) và \(g_{i}\). Bạn được cho một số nguyên \(t\).

Bạn cần chọn ra một đỉnh \(r\) cùng một dãy các đỉnh \(s_{1}, s_{2}, \ldots, s_{k}\) thoả mãn các điều kiện dưới đây:

• Các đỉnh \(s_{1}, s_{2}, \ldots, s_{k}\) là \(k\) đỉnh đôi một phân biệt thuộc cây con gốc \(r\) (\(k\) đỉnh này có thể chứa hoặc không chứa đỉnh \(r\)).
• \(w_{s_{1}} + w_{s_{2}} + \ldots + w_{s_{k}} \leq t\).
• Giá trị \(b_{r} + k^{2}\) là lớn nhất có thể.
• Nếu có nhiều phương án thoả mãn mọi điều kiện trên, ta chọn phương án có \(k\) nhỏ nhất.
• Nếu có nhiều phương án thoả mãn mọi điều kiện trên, ta chọn phương án có dãy
  \((g_{s_{1}}, g_{s_{2}}, \ldots, g_{s_{k}})\) có thứ tự từ điển nhỏ nhất.

Nhắc lại, dãy số \(x_{1}, x_{2}, \ldots, x_{m}\) có thứ tự từ điển nhỏ hơn dãy số \(y_{1}, y_{2}, \ldots, y_{m}\) khi và chỉ khi tồn tại chỉ số \(\alpha\) sao cho:

• \(1 \leq \alpha \leq m, x_{\alpha} < y_{\alpha}\), và
• \(x_{\beta} = y_{\beta} \forall 1 \leq \beta \leq \alpha − 1\).

Input

• Dòng đầu tiên chứa hai số nguyên \(\theta\) và \(\tau\) lần lượt là số thứ tự của subtask chứa test này và số bộ dữ liệu có trong file dữ liệu. Sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai chứa hai số nguyên \(n\) và \(t\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq t \leq 10^{17})\).
  • Dòng thứ ba chứa \(n − 1\) số nguyên \(p_{2}, p_{3}, \ldots, p_{n}\) \((1 \leq p_{i} < i)\).
  • Dòng thứ tư chứa \(n\) số nguyên \(w_{1}, w_{2}, \ldots, w_{n}\) \((1 \leq w_{i} \leq 10^{7})\).
  • Dòng thứ năm chứa \(n\) số nguyên \(b_{1}, b_{2}, \ldots, b_{n}\) \((1 \leq b_{i} \leq 10^{11})\).
  • Dòng thứ sáu chứa \(n\) số nguyên \(g_{1}, g_{2}, \ldots, g_{n}\) \((1 \leq g_{i} \leq 10^{13})\).
• Gọi \(N\) là tổng giá trị của \(n\) trong tất cả các bộ dữ liệu, dữ liệu vào đảm bảo \(N \leq 10_{6}\).

Output

• Với mỗi bộ dữ liệu, ghi ra kết quả trên hai dòng:
  • Dòng đầu tiên chứa hai số nguyên \(b_{r} + k^{2}\) và \(k\).
  • Dòng thứ hai chứa \(k\) số nguyên \(g_{s_{1}}, g_{s_{2}}, \ldots, g_{s_{k}}\).

Scoring

• Subtask \(1\) (\(12\) điểm): \(n \leq 20\) và \(N \leq 10^{2}\).
• Subtask \(2\) (\(10\) điểm): \(n \leq 2000\) và \(N \leq 10^{4}\).
• Subtask \(3\) (\(8\) điểm): \(w_{1} = w_{2} = \ldots = w_{n}\).
• Subtask \(4\) (\(9\) điểm): \(b_{1} = b_{2} = \ldots = b_{n}\).
• Subtask \(5\) (\(13\) điểm): \(g_{1} = g_{2} = \ldots = g_{n}\).
• Subtask \(6\) (\(11\) điểm): \(p_{i} = i − 1\) với mọi \(2 \leq i \leq n\).
• Subtask \(7\) (\(7\) điểm): Không có ràng buộc gì thêm.

Example

1 1

13 7
1 1 1 2 2 2 3 3 3 3 4 4
2 2 2 2 2 2 2 2 2 2 2 3 3
1 6 6 9 9 8 7 6 5 4 3 2 1
13 12 11 10 9 8 7 6 5 4 3 2 1

15 3
3 4 5

Bạn cần chọn ra một đỉnh \(r\) cùng một dãy các đỉnh \(s_{1}, s_{2}, \ldots, s_{k}\) thoả mãn các điều kiện dưới đây:

• Các đỉnh \(s_{1}, s_{2}, \ldots, s_{k}\) là \(k\) đỉnh đôi một phân biệt thuộc cây con gốc \(r\) (\(k\) đỉnh này có thể chứa hoặc không chứa đỉnh \(r\)).
• \(w_{s_{1}} + w_{s_{2}} + \ldots + w_{s_{k}} \leq t\).
• Giá trị \(b_{r} + k^{2}\) là lớn nhất có thể.
• Nếu có nhiều phương án thoả mãn mọi điều kiện trên, ta chọn phương án có \(k\) nhỏ nhất.
• Nếu có nhiều phương án thoả mãn mọi điều kiện trên, ta chọn phương án có dãy
  \((g_{s_{1}}, g_{s_{2}}, \ldots, g_{s_{k}})\) có thứ tự từ điển nhỏ nhất.

Nhắc lại, dãy số \(x_{1}, x_{2}, \ldots, x_{m}\) có thứ tự từ điển nhỏ hơn dãy số \(y_{1}, y_{2}, \ldots, y_{m}\) khi và chỉ khi tồn tại chỉ số \(\alpha\) sao cho:

• \(1 \leq \alpha \leq m, x_{\alpha} < y_{\alpha}\), và
• \(x_{\beta} = y_{\beta} \forall 1 \leq \beta \leq \alpha − 1\).

Input

• Dòng đầu tiên chứa hai số nguyên \(\theta\) và \(\tau\) lần lượt là số thứ tự của subtask chứa test này và số bộ dữ liệu có trong file dữ liệu. Sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai chứa hai số nguyên \(n\) và \(t\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq t \leq 10^{17})\).
  • Dòng thứ ba chứa \(n − 1\) số nguyên \(p_{2}, p_{3}, \ldots, p_{n}\) \((1 \leq p_{i} < i)\).
  • Dòng thứ tư chứa \(n\) số nguyên \(w_{1}, w_{2}, \ldots, w_{n}\) \((1 \leq w_{i} \leq 10^{7})\).
  • Dòng thứ năm chứa \(n\) số nguyên \(b_{1}, b_{2}, \ldots, b_{n}\) \((1 \leq b_{i} \leq 10^{11})\).
  • Dòng thứ sáu chứa \(n\) số nguyên \(g_{1}, g_{2}, \ldots, g_{n}\) \((1 \leq g_{i} \leq 10^{13})\).
• Gọi \(N\) là tổng giá trị của \(n\) trong tất cả các bộ dữ liệu, dữ liệu vào đảm bảo \(N \leq 10_{6}\).

Output

• Với mỗi bộ dữ liệu, ghi ra kết quả trên hai dòng:
  • Dòng đầu tiên chứa hai số nguyên \(b_{r} + k^{2}\) và \(k\).
  • Dòng thứ hai chứa \(k\) số nguyên \(g_{s_{1}}, g_{s_{2}}, \ldots, g_{s_{k}}\).

Scoring

• Subtask \(1\) (\(12\) điểm): \(n \leq 20\) và \(N \leq 10^{2}\).
• Subtask \(2\) (\(10\) điểm): \(n \leq 2000\) và \(N\) \leq \(10^{4}\).
• Subtask \(3\) (\(8\) điểm): \(w_{1} = w_{2} = \ldots = w_{n}\).
• Subtask \(4\) (\(9\) điểm): \(b_{1} = b_{2} = \ldots = b_{n}\).
• Subtask \(5\) (\(13\) điểm): \(g_{1} = g_{2} = \ldots = g_{n}\).
• Subtask \(6\) (\(11\) điểm): \(p_{i} = i − 1\) với mọi \(2 \leq i \leq n\).
• Subtask \(7\) (\(7\) điểm): Không có ràng buộc gì thêm.

Example

1 1

13 7
1 1 1 2 2 2 3 3 3 3 4 4
2 2 2 2 2 2 2 2 2 2 2 3 3
1 6 6 9 9 8 7 6 5 4 3 2 1
13 12 11 10 9 8 7 6 5 4 3 2 1

15 3
3 4 5