Folding Paper Crease Query

Little X has applied for a Guinness World Record, but because he is in quarantine he cannot provide physical evidence. He allowed the organization to ask t queries. In each query, a paper is folded n times according to a given binary string s (of length n) and then unfolded (the paper retains only the crease marks).

The folding process is as follows. For the i-th fold, if \( s_i = 0 \), the paper is folded from left to right (so that the left side aligns with the right side). If \( s_i = 1 \), the paper is folded from right to left (so that the right side aligns with the left side). In all folds, the fold is performed by flipping the paper from above.

After unfolding, creases remain in their original positions. The query asks: what is the type of the k-th crease from the left – is it a mountain fold (a peak, here denoted by Up) or a valley fold (a trough, here denoted by Down)? Output Up if the crease is a mountain fold and Down otherwise.

The crease pattern can be constructed recursively. Let \( F(0) \) be an empty sequence. For each fold \( i=1,2,\dots,n \), the crease pattern \( F(i) \) is formed from \( F(i-1) \) by appending a new crease and then the mirror of \( F(i-1) \) with inverted crease types. Specifically, if we denote the crease corresponding to the i-th fold by:

[ \text{new crease} = \begin{cases}\text{Down} & \text{if } s_i = 0, \ \text{Up} & \text{if } s_i = 1, \end{cases} ]

then the recurrence is

[ F(i) = F(i-1) ;\Vert; (\text{new crease}) ;\Vert; \text{invert}(\text{reverse}(F(i-1))), ]

where \( \text{invert}(\cdot) \) swaps Up and Down, and \( \Vert \) denotes concatenation. After n folds, the crease pattern has length \( 2^n - 1 \). A recursive observation is that the middle crease (at position \( 2^{n-1} \)) is exactly the crease created by the n-th fold, and the rest of the creases mirror the previous folding pattern. Using this, one can determine the type of the k-th crease recursively.

inputFormat

The first line contains one integer t (the number of queries). Each query consists of two lines. The first line of a query contains two integers n and k, where n (\(1 \le n\le\text{small enough}\)) is the number of folds and k (1-indexed) is the position of the crease (from the left) whose type is to be determined. The second line contains a binary string s of length n; for the i-th fold, if \( s_i = 0 \), the paper is folded from left to right, and if \( s_i = 1 \), the paper is folded from right to left.

outputFormat

For each query, output a single line containing either Up (if the k-th crease is a mountain fold) or Down (if it is a valley fold).

sample

1
1 1
0

Down