本文共 6255 字，大约阅读时间需要 20 分钟。

哈哈哈看来许个愿还是很有用的，昨天许愿自己今天可以过三个题，今天竟然真的过了三个题，还是很开心的。补一下今天做的题目。

You are given a binary string of length nn (i. e. a string consisting of nn characters '0' and '1').

In one move you can swap two adjacent characters of the string. What is the lexicographically minimum possible string you can obtain from the given one if you can perform no more than kk moves? It is possible that you do not perform any moves at all.

Note that you can swap the same pair of adjacent characters with indices ii and i+1i+1 arbitrary (possibly, zero) number of times. Each such swap is considered a separate move.

You have to answer qq independent test cases.

Input

The first line of the input contains one integer qq (1≤q≤1041≤q≤104) — the number of test cases.

The first line of the test case contains two integers nn and kk (1≤n≤106,1≤k≤n21≤n≤106,1≤k≤n2) — the length of the string and the number of moves you can perform.

The second line of the test case contains one string consisting of nn characters '0' and '1'.

It is guaranteed that the sum of nn over all test cases does not exceed 106106 (∑n≤106∑n≤106).

Output

For each test case, print the answer on it: the lexicographically minimum possible string of length nnyou can obtain from the given one if you can perform no more than kk moves.

Example

Input

38 5110110107 911111007 111111100

Output

0101111001011110011111

Note

In the first example, you can change the string as follows: 110−−11010→10−−111010→011110−−10→01110−−110→0110−−1110→01011110110_11010→10_111010→011110_10→01110_110→0110_1110→01011110.

In the third example, there are enough operations to make the string sorted.

 这一道题目我最开始的做法是从头到尾遍历k次，每次从头开始通过贪心思想将零尽可能地提前，这样就能符合题意，到那时我在最开始做的时候因为遍历方法的问题导致如果k足够大时，我每次只要找到零就交换，就导致最后的零根本没有机会和前面的数字交换，就采用了新的遍历方法，定义了一个cnt，每次在交换前都进行一次判断，这样就避免了只要碰见零就交换的情况

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;ll t,n;ll b,s,k;char ch[1000010];ll pd[1000010];int main(){ std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>t; while(t--) { cin>>n>>k; cin>>ch; ll cnt=0; for (ll i=0;i
        
       
      
     
    
   

There is a river of width nn. The left bank of the river is cell 00 and the right bank is cell n+1n+1 (more formally, the river can be represented as a sequence of n+2n+2 cells numbered from 00 to n+1n+1). There are also mm wooden platforms on a river, the ii-th platform has length cici (so the ii-th platform takes ciciconsecutive cells of the river). It is guaranteed that the sum of lengths of platforms does not exceed nn.

You are standing at 00 and want to reach n+1n+1 somehow. If you are standing at the position xx, you can jump to any position in the range [x+1;x+d][x+1;x+d]. However you don't really like the water so you can jump only to such cells that belong to some wooden platform. For example, if d=1d=1, you can jump only to the next position (if it belongs to the wooden platform). You can assume that cells 00 and n+1n+1belong to wooden platforms.

You want to know if it is possible to reach n+1n+1 from 00 if you can move any platform to the left or to the right arbitrary number of times (possibly, zero) as long as they do not intersect each other (but two platforms can touch each other). It also means that you cannot change the relative order of platforms.

Note that you should move platforms until you start jumping (in other words, you first move the platforms and then start jumping).

For example, if n=7n=7, m=3m=3, d=2d=2 and c=[1,2,1]c=[1,2,1], then one of the ways to reach 88 from 00 is follow:

 The first example: n=7n=7.

Input

The first line of the input contains three integers nn, mm and dd (1≤n,m,d≤1000,m≤n1≤n,m,d≤1000,m≤n) — the width of the river, the number of platforms and the maximum distance of your jump, correspondingly.

The second line of the input contains mm integers c1,c2,…,cmc1,c2,…,cm (1≤ci≤n,∑i=1mci≤n1≤ci≤n,∑i=1mci≤n), where cici is the length of the ii-th platform.

Output

If it is impossible to reach n+1n+1 from 00, print NO in the first line. Otherwise, print YES in the first line and the array aa of length nn in the second line — the sequence of river cells (excluding cell 00 and cell n+1n+1).

If the cell ii does not belong to any platform, aiai should be 00. Otherwise, it should be equal to the index of the platform (11-indexed, platforms are numbered from 11 to mm in order of input) to which the cell iibelongs.

Note that all aiai equal to 11 should form a contiguous subsegment of the array aa of length c1c1, all aiai equal to 22 should form a contiguous subsegment of the array aa of length c2c2, ..., all aiai equal to mm should form a contiguous subsegment of the array aa of length cmcm. The leftmost position of 22 in aa should be greater than the rightmost position of 11, the leftmost position of 33 in aa should be greater than the rightmost position of 22, ..., the leftmost position of mm in aa should be greater than the rightmost position of m−1m−1.

See example outputs for better understanding.

Examples

Input

7 3 21 2 1

Output

YES0 1 0 2 2 0 3

Input

10 1 111

Output

YES0 0 0 0 0 0 0 0 0 1

Input

10 1 52

Output

YES0 0 0 0 1 1 0 0 0 0

Note

Consider the first example: the answer is [0,1,0,2,2,0,3][0,1,0,2,2,0,3]. The sequence of jumps you perform is 0→2→4→5→7→80→2→4→5→7→8.

Consider the second example: it does not matter how to place the platform because you always can jump from 00 to 1111.

Consider the third example: the answer is [0,0,0,0,1,1,0,0,0,0][0,0,0,0,1,1,0,0,0,0]. The sequence of jumps you perform is 0→5→6→110→5→6→11.

这就是一道典型的贪心题目，题意是给定一个长度的水沟，和m块木板，还有一次可以跳跃的距离。以及每块模板的长度。

当然因为时贪心题目，所以我每次贪心的都跳最大的距离d，但是存在一种特殊情况，就是如果每次跳过d会超过所需的距离我们就要重新选择贪心策略。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n,t,m,d,sum,s1;int ans[100001];int ls[100001];int c[100001];int main(){ cin>>n>>m>>d; sum=0; for(int i=1;i<=m;i++) { cin>>c[i]; sum+=(c[i]-1); } ls[m]=c[m]; for(int i=m-1;i>=1;i--) ls[i]=c[i]+ls[i+1]; if(d*(m+1)