No.3274 Arithmetic Right Shift
Problem Statement
You are given a positive integer $K$ and a string $S$ consisting of 0, 1.
Here, the following operation on $S$ is called an arithmetic right shift.
Insert the $1$-st character of $S$ at the beginning of $S$. Then, delete $1$ character from the end of $S$.
Find $S$ after performing the arithmetic right shift exactly $K$ times.
You are given $T$ test cases; answer each of them.
Constraints
- $T$ is an integer.
- $1 \le T \le 10^4$.
- $K$ is an integer.
- $1 \le K \le10^9$.
- $S$ is a string consisting of
0,1. - $1 \le |S| \le 64 \enspace (|S|$ is the length of $S$ $)$.
Input
The input is given from Standard Input in the following format. Here, $\mathrm{case}_i ~ (1 \le i \le T)$ is the $i$-th test case.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.
$K$ $S$
Output
Print $T$ lines. On the $i ~ (1 \le i \le T)$-th line, print the answer for the $i$-th test case.
Sample
Sample
Input
4 2 0110 5 10101010 998244353 01 9 1101000000000111
Output
0001 11111101 00 1111111111101000
For the $1$-st test case, the arithmetic right shift is performed $2$ times by the following procedure. Here, let $S_1$ be the $1$-st character of $S$.
- Insert $S_1 =$
0at the beginning of $S =$0110, and delete the last character of $S$. This updates it to $S =$0011. - Insert $S_1 =$
0at the beginning of $S =$0011, and delete the last character of $S$. This updates it to $S =$0001.
Performing the operations in this way, you can obtain 0001.
For the $2$-nd test case, performing $5$ times the operation of inserting $S_1 =$ 1 at the beginning of $S$ and deleting the last character of $S$, you can obtain 11111101.
For the $3$-rd test case, note the case where the number of arithmetic right shifts to perform is huge.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。