Recently, Chef found a new formula for computing powers of a sequence:
- You are given two sequences $A_1, A_2, \ldots, A_N$ and $(l_1, r_1), (l_2, r_2), \ldots, (l_N, r_N)$.
- The $1$-st power of the sequence $A$ is $A^1 = A$.
- For each $k > 1$, the $k$-th power of the sequence $A$ (denoted by $A^k$) is a sequence with length $N$ such that for each valid $i$, the $i$-th element of this sequence is (Ak)i=(Ak−1)li⊕(Ak−1)li+1⊕…⊕(Ak−1)ri−1⊕(Ak−1)ri.(Ak)i=(Ak−1)li⊕(Ak−1)li+1⊕…⊕(Ak−1)ri−1⊕(Ak−1)ri.(A^k)_i = (A^{k-1})_{l_i} \oplus (A^{k-1})_{l_i+1} \oplus \ldots \oplus (A^{k-1})_{r_i-1} \oplus (A^{k-1})_{r_i} \,.
After discovering this new formula, Chef tried to find $A^K$, but he felt that it is very time consuming. Therefore, Chef wants you to do it. Can you find the $K$-th power of $A$ for Chef?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $l_i$ and $r_i$.

-----Output-----
For each test case, print a single line containing $N$ space-separated integers $(A^K)_1, (A^K)_2, \ldots, (A^K)_N$.

-----Constraints-----
- $1 \le T \le 3$
- $1 \le N \le 500$
- $1 \le K \le 5 \cdot 10^7$
- $1 \le A_i \le 10^{18}$ for each valid $i$
- $1 \le l_i \le r_i \le N$ for each valid $i$

-----Subtasks-----
Subtask #1 (50 points):
- $T = 1$
- $N \le 100$
Subtask #2 (50 points): original constraints

-----Sample Input-----
1
3 2
1 2 3
1 2
2 3
1 3

-----Example Ouput-----
3 1 0

-----Explanation-----
Example case 1:
- $(A^2)_1 = A_1 \oplus A_2 = 1 \oplus 2 = 3$
- $(A^2)_2 = A_2 \oplus A_3 = 2 \oplus 3 = 1$
- $(A^2)_3 = A_1 \oplus A_2 \oplus A_3 =1 \oplus 2 \oplus 3 = 0$

Difficulty: interview

Starter code:

Solutions:
import numpy as np

def solve(n,k,a,l,r):
    shape = (n,n)
    mat = np.zeros(shape, dtype=np.int64)
    for i in range(n):
        for j in range(l[i], r[i]):
            mat[i][j]=1
    
    ans = np.eye(n,n, dtype=np.int64)
    while(k>0):
        if k%2 == 1:
            ans = np.matmul(mat, ans)
            ans%=2
        mat = np.matmul(mat, mat)
        mat%=2
        k = k//2
    result = []
    for i in range(n):
        aux = 0
        for j in range(n):
            if ans[i][j] == 1:
                aux^=a[j]
        result.append(aux)
    return result
        




t = int(input())
for i in range(t):
    s = input().split()
    n = int(s[0])
    k = int(s[1])
    a = []
    l = []
    r = []
    s = input().split()
    for i in range(n):
        a.append(int(s[i]))
    for i in range(n):
        s = input().split()
        l.append(int(s[0])-1)
        r.append(int(s[1]))
    arr = solve(n,k-1,a,l,r)
    s = ""
    for e in arr:
        s += str(e)
        s +=" "
    print(s)


# cook your dish here
import sys
import math
from collections import Counter
from heapq import heapify, heappop, heappush
import numpy as np

# sys.setrecursionlimit(10**6)
# input = sys.stdin.buffer.readline

MAX_INT = 2**62-1
MOD = 10**9 + 7


def __starting_point():
    T = int(input())
    for _ in range(T):
        n, k = map(int, input().split())
        nums = np.array([int(s) for s in input().split()], dtype=np.int)
        ranges = []
        for _ in range(n):
            l, r = map(int, input().split())
            ranges.append((l-1, r-1))

        mat = np.zeros((n, n), dtype='u1')

        for i, (l, r) in enumerate(ranges):
            mat[i, l:r+1] = 1

        trans = np.eye(n, dtype='u1')
        k -= 1
        while k:
            if k & 1:
                trans = trans @ mat
                trans &= 1
            k >>= 1
            mat = mat @ mat
            mat &= 1
            # print(k, trans)
        # print(trans)

        ans = np.zeros((n,), dtype=np.int)
        for i in range(60)[::-1]:
            c = (nums >> i) & 1
            ans <<= 1
            ans += (trans @ c & 1)
        print(*ans, sep=' ')





__starting_point()