Nông dân John đã tiến hành một nghiên cứu về sự tiến hóa của các giống bò khác nhau. Kết quả là một cây có gốc với \(N\) (\(1 \leq N \leq 10^5\)) nút đánh số từ \(1\) đến \(N\), mỗi nút tương ứng với một giống bò. Với mỗi \(i \in [2, N]\), nút cha của \(i\) là nút \(p_i\) (\(1 \leq p_i < i\)), nghĩa là giống \(i\) tiến hóa từ giống \(p_i\). Nút \(j\) được gọi là tổ tiên của nút \(i\) nếu \(j = p_i\) hoặc \(j\) là tổ tiên của \(p_i\).

Mỗi nút \(i\) tương ứng với giống bò được gán số nguyên \(s_i\). Sự "mất cân bằng" của cây là giá trị lớn nhất của \(|s_i - s_j|\) trên tất cả các cặp nút \((i, j)\) với \(j\) là tổ tiên của \(i\).

Nông dân John không biết giá trị chính xác của \(s_i\) của mỗi giống, nhưng ông biết giới hạn dưới và giới hạn trên của những giá trị này. Công việc của bạn là gán giá trị nguyên của \(s_i \in [l_i, r_i]\) (\(0 \leq l_i \leq r_i \leq 10^9\)) cho mỗi nút sao cho sự mất cân bằng của cây là nhỏ nhất.

Input

• Dòng đầu tiên chứa số \(T\) (\(1 \leq T \leq 10\)) - số lượng bộ dữ liệu, và số nguyên \(B \in \{0, 1\}\).
• Với mỗi bộ dữ liệu:
  • Dòng đầu tiên chứa số \(N\), sau đó là \(N-1\) số nguyên \(p_2, p_3, \dots, p_N\).
  • \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i\).
• Dữ liệu đảm bảo tổng \(N\) của tất cả các bộ dữ liệu không vượt quá \(10^5\).

Output

Với mỗi bộ dữ liệu, in ra \(1\) hoặc \(2\) dòng dựa vào giá trị của \(B\):

• Dòng đầu in ra độ mất cân bằng nhỏ nhất.
• Nếu \(B = 1\), dòng thứ \(2\) in ra \(N\) số nguyên \(s_1, s_2, \dots, s_N\) cách nhau bởi dấu cách.

Example

3 0
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

3
1
4

3 1
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

3
3 1 6
1
6 5 5 5 5
4
5 1 9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(l_i = r_i\) với mọi \(i\).
• Subtask \(2\) (\(20\%\) số điểm): \(p_i = i - 1\) với mọi \(i\).
• Subtask \(3\) (\(60\%\) số điểm): Không có điều kiện gì thêm.
• Với mỗi subtask, một nửa số điểm sẽ có \(B = 0\), nửa còn lại sẽ có \(B = 1\).