Let two functions be the following:

$$ f(n) = a_1 \times f(n-1) + b_1 \times f(n-2) + c_1 \times g(n-3) \\ g(n) = a_2 \times g(n-1) + b_2 \times g(n-2) + c_2 \times f(n-3) $$

Find f_n % M and g_n % M. (% stands for the modulo operation.)

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a blank line. Next line contains three integers a₁ b₁ c₁ (0 ≤ a₁, b₁, c₁ < 25000). Next line contains three integers a₂ b₂ c₂ (0 ≤ a₂, b₂, c₂ < 25000). Next line contains three integers f₀ f₁ f₂ (0 ≤ f₀, f₁, f₂ < 25000). Next line contains three integers g₀ g₁ g₂ (0 ≤ g₀, g₁, g₂ < 25000). The next line contains an integer M (1 ≤ M < 25000).

Next line contains an integer q (1 ≤ q ≤ 100) denoting the number of queries. Next line contains q space separated integers denoting n. Each of these integers is non-negative and less than 2³¹.

For each case, print the case number in a line. Then for each query, you have to print one line containing f_n % M and g_n % M.