DPEQN - Congruence Equation

no tags 

Given a congruence equation:

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

In which, a1, a2, ..., an, b and m are positive integer constants; x1, x2, ..., xn 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 a1, a2, ..., an (1 ≤ ai ≤ 108)
  • Line 3: b, m (1 ≤ b, m ≤ 108)

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 x1, x2, ..., xn (0 ≤ xi < 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

hide comments
Anshu Avinash: 2011-09-24 11:48:13

Are all possible solutions accepted?

Tasnim Imran Sunny: 2010-04-21 18:33:06

..

Last edit: 2010-04-21 18:38:38

Added by:Duc
Date:2008-10-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:© VNOI