Giải bài trực tuyến

Given a congruence equation:

a1x1 + ... a2x2 + ... + anxn = b (mod m)

In which, a₁, a₂, ..., a_n, b and m are positive integer constants; x₁, x₂, ..., x_n are unknowns.

Find a solution for this equation, or show that the equation has no solution.

Input

First line: number of test cases. Each test case has the following form:

• Line 1: n (1 ≤ n ≤ 100)
• Line 2: n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁸)
• Line 3: b, m (1 ≤ b, m ≤ 10⁸)

Each test case is separated by a blank line.

Output

For each test case, if the equation has no solution, print "NO". Otherwise, print n integers x₁, x₂, ..., x_n (0 ≤ x_i < m) that is one solution to the equation.

Example

Input
2

2
4 6
6 10

2
4 6
3 8

Output
1 2
NO