AT_abc443_e [ABC443E] Climbing Silver

There is an $ N \times N $ grid. The cell at the $ i $ -th row from the top and $ j $ -th column from the left is called $ (i,j) $ . The grid is described by $ N $ strings $ S_1,S_2,\dots,S_N $ . If the $ j $ -th character of $ S_i $ is `.`, $ (i,j) $ is an empty cell; if it is `#`, $ (i,j) $ is a wall cell. Initially, Takahashi-kun is at empty cell $ (N,C) $ , and repeats the following movement $ N-1 $ times: - If he is currently at $ (r,c) $ , he specifies one of $ (r-1,c-1),(r-1,c),(r-1,c+1) $ as the destination. Here, he cannot specify a cell that does not exist in the grid as the destination. - If the destination $ (a,b) $ is a wall cell, the following occurs: - If $ (i,b) $ is currently an empty cell for all integers satisfying $ a < i \le N $ , he destroys the wall at $ (a,b) $ and moves there. That is, $ (a,b) $ becomes an empty cell and he moves to $ (a,b) $ . - Otherwise, he fails to move. In this case, he immediately ends the repetition of movements, even if he has not made $ N-1 $ movements. - If the destination $ (a,b) $ is an empty cell, he moves to $ (a,b) $ . Output a string $ R $ of length $ N $ satisfying the following conditions: - If he can reach $ (1,i) $ without failing during the movements, the $ i $ -th character of $ R $ is `1`. - Otherwise, the $ i $ -th character of $ R $ is `0`. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ C $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

Print $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 This input contains five test cases. For the first test case, for example, he can reach $ (1,3) $ without failing during the movements as follows: - Initially, he is at $ (5,3) $ . - He moves to empty cell $ (4,2) $ . - $ (3,3) $ is a wall cell, but since $ (4,3),(5,3) $ are currently both empty cells, he destroys the wall at $ (3,3) $ and moves to $ (3,3) $ . - $ (2,3) $ is a wall cell, but since $ (3,3),(4,3),(5,3) $ are currently all empty cells, he destroys the wall at $ (2,3) $ and moves to $ (2,3) $ . - $ (1,3) $ is a wall cell, but since $ (2,3),(3,3),(4,3),(5,3) $ are currently all empty cells, he destroys the wall at $ (1,3) $ and moves to $ (1,3) $ . He can reach $ (1,1),(1,3),(1,4),(1,5) $ without failing during the movements, so print `10111`. ### Constraints - $ T,N,C $ are integers. - $ 1 \le T \le 50000 $ - $ 2 \le N \le 3000 $ - $ 1 \le C \le N $ - $ S_i $ is a string of length $ N $ consisting of `.` and `#`. - The $ C $ -th character of $ S_N $ is `.`. - For each input, the sum of $ N^2 $ does not exceed $ 9 \times 10^6 $ .