Background

Guinness record: a sheet of paper (if nearly $4$ kilometers of toilet paper can be counted as one sheet) can be folded in half at most $13$ times. Little X bragged that he broke this record, but he exaggerated too much.

Problem Description

Little X applied for this record to the Guinness World Records organization, but he happened to be quarantined at home and could not prove it. He had to allow them to ask $t$ questions to confirm that he truly broke the record.

For each question, they can ask Little X to fold a sheet of paper in half $n$ times following the rules given by a $01$ string $s$, and then unfold it. For the $i$-th fold, if $s_i = 0$, fold the paper from left to right so that the left side aligns with the right side; if $s_i = 1$, fold the paper from right to left so that the right side aligns with the left side. All folds are made by flipping from the top. Then it will be unfolded. After unfolding, the paper stays in its original position, only keeping the creases. Check whether you can achieve this.

They want to know whether the $k$-th crease from left to right is an up crease (a crease that protrudes upward) or a down crease (a crease that dents downward). If the answer to the query is an up crease, output Up; otherwise output Down. Please help the poor Little X.

Illustrations of up creases and down creases can be found in the sample explanation.

Input Format

This problem uses multiple test cases.

The first line contains a positive integer $t$, the number of test cases.

The next $2t$ lines describe the test cases, with each test case taking two lines. For each test case, the first line contains two positive integers $n, k$. The next line contains a $01$ string of length $n$, representing $s$.

Output Format

Output $t$ lines. Each line contains one string, representing the answer for that test case.

7
3 1
010
3 2
010
3 3
010
3 4
010
3 5
010
3 6
010
3 7
010

Down
Up
Up
Down
Down
Down
Up

7
3 1
011
3 2
011
3 3
011
3 4
011
3 5
011
3 6
011
3 7
011

Down
Up
Up
Down
Down
Down
Up

2
13 114
1101101111010
13 514
1101101111010

Up
Up

Hint

Sample Explanation

Explanation for Sample #1:

Dynamic link: here. For some reason it cannot be displayed on Luogu.

Due to technical reasons, the GIF has a relatively low frame rate.

For Sample #2, please simulate manually.

Constraints

This problem uses bundled testdata.

• Subtask 1 ($20$ pts): $t = 10$, $1 \le n \le 5$.
• Subtask 2 ($80$ pts): $t = 10^5$.

For $100\%$ of the testdata, $1 \le t \le 10^5$, $1 \le n \le 60$, $1 \le k < 2^n$.

Translated by ChatGPT 5