Yue đang đi lạc trong bình nguyên vô tận, mà thầy giáo Settings cứ nhắc cô hoàn thành bài tập code của mình. Thầy giao cho cô bài tập như sau:

Cho một dãy \(a\) gồm \(n\) phần tử có một số phần tử không xác định là \(-1\). Nhiệm vụ của Yue là thay đổi các số \(-1\) thành các số nguyên không âm sao cho giá trị \(|b_1 + b_2 + \dots + b_{n - 1}|\) đạt giá trị nhỏ nhất.

Ta định nghĩa ở đây difference array là mảng \(b\) gồm \(n - 1\) phần tử, \(b_i = a_{i + 1} - a_i\) (\(1 \le i \le n - 1\)).

Hãy điền tất cả chỗ trống và in ra giá trị nhỏ nhất của \(|b_1 + b_2 + \dots + b_{n - 1}|\), ngoài ra in ra mảng \(a\) sau khi đã điền. Nếu có nhiều mảng \(a\) thỏa mãn, in ra mảng có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên \(t\) là số lượng bộ test (\(1 \le t \le 10^4\)).
• Mỗi bộ test gồm hai dòng:
  • Dòng đầu tiên chứa số nguyên \(n\) (\(2 \le n \le 2 \cdot 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-1 \le a_i \le 10^9\)), trong đó \(-1\) đại diện cho ô trống cần điền.

Tổng \(n\) của tất cả các bộ test không vượt quá \(2 \cdot 10^5\).

Output

• Với mỗi bộ test, in ra hai dòng:
  • Dòng đầu tiên là giá trị nhỏ nhất của \(|b_1 + b_2 + \dots + b_{n - 1}|\).
  • Dòng thứ hai là \(n\) số nguyên của mảng \(a\) sau khi đã điền các số \(-1\).

Example

6
4
2 -1 7 1
4
-1 2 4 -1
8
2 -1 1 5 11 12 1 -1
3
-1 -1 -1
3
2 5 4
2
-1 5

1
2 0 7 1
0
0 2 4 0
0
2 0 1 5 11 12 1 2
0
0 0 0
2
2 5 4
0
5 5

Constraints

• \(1 \le t \le 10^4\)
• \(2 \le n \le 2 \cdot 10^5\)
• \(-1 \le a_i \le 10^9\)
• Tổng \(n\) trong tất cả các bộ test không quá \(2 \cdot 10^5\).