cho.sh

Window XOR

아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

길이가 NN인 수열 XX가 주어진다. 11이상 NN이하의 정수 KK가 주어질 때, XX를 한 번 변환하면 수열의 각 값은 다음과 같이 바뀐다. X′X'은 변환된 이후의 수열이며, ⊕\oplus는 Bitwise-XOR연산이다.

 X′_1=X_1⊕X_2⊕⋯⊕X_KX'\_1 = X\_1 \oplus X\_2 \oplus \cdots \oplus X\_K X′_2=X_2⊕X_3⊕⋯⊕X_K+1X'\_2 = X\_2 \oplus X\_3 \oplus \cdots \oplus X\_{K+1} ⋮\vdots X′_N−K+1=X_N−K+1⊕X_N−K+2⊕⋯⊕X_N−1⊕X_NX'\_{N-K+1} = X\_{N-K+1} \oplus X\_{N-K+2} \oplus \cdots \oplus X\_{N-1} \oplus X\_N X′_N−K+2=X_N−K+2⊕X_N−K+3⊕⋯⊕X_N⊕X_1X'\_{N-K+2} = X\_{N-K+2} \oplus X\_{N-K+3} \oplus \cdots \oplus X\_{N} \oplus X\_1 ⋮\vdots X′_N−1=X_N−1⊕X_N⊕⋯⊕X_K−3 ⊕X_K−2X'\_{N-1} = X\_{N-1} \oplus X\_N \oplus \cdots \oplus X\_{K-3}  \oplus X\_{K-2} X′_N=X_N⊕X_1⊕⋯⊕X_K−2 ⊕X_K−1X'\_{N} = X\_{N} \oplus X\_1 \oplus \cdots \oplus X\_{K-2}  \oplus X\_{K-1} 

조금 더 편하게 표현하자면, X_i+N=X_iX\_{i+N} = X\_i으로 봤을 때, X′_i=X_i⊕⋯⊕X_i+K−1X'\_i = X\_i \oplus \cdots \oplus X\_{i+K-1}인 것이다.

수열 XX와 KK가 주어질 때, 수열 XX를 TT번 변환한 수열을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 세 정수 NN, KK, TT(1≤K≤N≤1051 ≤ K ≤ N ≤ 10^5, 1≤T≤10181 ≤ T ≤ 10^{18})가 공백 하나로 구분되어 주어진다.

두 번째 줄에는 NN개의 정수 X_1,X_2,⋯ ,X_NX\_1, X\_2, \cdots , X\_N(0≤X_i≤1090 ≤ X\_i ≤ 10^9)이 공백 하나로 구분되어 주어진다.

출력

주어진 XX를 TT번 변환한 수열을 AA라고 할 때, 첫 번째 줄에 A_1A\_1에서 A_NA\_N까지의 NN개의 정수를 공백 하나로 구분하여 순서대로 출력한다.