Fill Missing Electricity Usage Data

You are given electricity usage data from various cities. In some cases, the data values are missing and represented as 'NA'. Your task is to fill in these missing values according to the following rule:

For every missing data point at index i, find the nearest non-missing value to its left and the nearest non-missing value to its right.

• If both exist, fill the missing value with (\lfloor (left + right) / 2 \rfloor) (i.e. integer division). • If only one exists, fill it with that value. • If neither exists, fill it with 0.

Each test case starts with an integer representing the number of data points (including the count itself) followed by the data points separated by spaces. Note that the first number is only for reference and should be ignored during the processing.

inputFormat

Input is read from standard input. The first line contains an integer T, the number of test cases. Each of the following T lines represents a test case. Each test case consists of several space-separated tokens where the first token is an integer N (the count of data points, not used in computation) and the next N tokens are either an integer or the string 'NA'.

outputFormat

For each test case, output a single line containing the processed data. The numbers should be separated by a single space. Results are printed to standard output.## sample

2
5 10 NA 30 40 50
4 NA 20 30 NA

10 20 30 40 50
20 20 30 30