Given a black and white image of n by n pixels, the algorithm works as follow:
For each pixel p at the i‐th row and the j‐th column (1+ r <= i, j <= n – r), its gray level g[i,j] is replace by the median of gray levels of pixels in the (2r+1) by (2r+1) square centered at p. The square is called the filtering window and r is its radius.

Considering the above example, the gray level of the pixel at center will be changed from 150 to 124, which is the median of a filtering window of radius 1.

Note that the algorithm won’t be applied on the pixels near the boundary, for the filtering window lies outside the image. So you are actually asked to output the filtered sub-image which contains the pixels from (r+1, r+1) to (n-r, n-r).

(a) The first line contains two integers, n and r, meaning that the size of image is n * n (3 <= n <= 500) and the radius of filtering window is r ( 3 <= 2r + 1 <= n).

(b) The following n lines contains the n by n gray level matrix presenting the image

(c) The gray level ranges from 0 to 1000000 The input ends by double 0s.

 //1781MS    6196K    2399 B    G++

 #include<stdio.h>

 #include<string.h>

 #define N 505

 int g[N][N];

 int ans[N][N];

 int c[<<];

 int n,r,M;

 inline int lowbit(int k)

 {

     return k&(-k);

 }

 int getsum(int k)

 {

     int s=;

     for(;k>;k-=lowbit(k))

         s+=c[k];

     return s;

 }

 void insert(int k,int detal)

 {

     for(;k<=M;k+=lowbit(k))

         c[k]+=detal;

 }

 int find_kth(int k) //树状数组找第k大的数

 {

     int sum=,pos=;

     for(int i=;i>=;i--){

         pos+=(<<i);

         if(pos>M || sum+c[pos]>=k)

             pos-=(<<i);

         else sum+=c[pos];

     }

     return pos+;

 }

 void solve()

 {

     int R=*r+;

     int k=R*R/+;

     for(int i=;i<=R;i++)

         for(int j=;j<=R;j++)

             insert(g[i][j],);

     //for(int i=1;i<=2*(k-1);i++) printf("*%d\n",c[i]);

     for(int i=r+;i<=n-r;i++){

         if((i-r)&){  //奇数行，向右遍历

             if(i!=r+){

                 for(int j=;j<=R;j++){

                     insert(g[i-r-][j],-);

                     insert(g[i+r][j],);

                 }

             }

             ans[i][r+]=find_kth(k);

             for(int j=r+;j<=n-r;j++){

                 for(int ii=i-r;ii<=i+r;ii++){

                     insert(g[ii][j-r-],-);

                     insert(g[ii][j+r],);

                 }

                 ans[i][j]=find_kth(k);

             }

         }else{ //偶数行，向左遍历

             for(int j=n;j>=n-R+;j--){

                 insert(g[i-r-][j],-);

                 insert(g[i+r][j],);

             }

             ans[i][n-r]=find_kth(k);

             for(int j=n-r-;j>=r+;j--){

                 for(int ii=i-r;ii<=i+r;ii++){

                     insert(g[ii][j+r+],-);

                     insert(g[ii][j-r],);

                 }

                 ans[i][j]=find_kth(k);

             }

         }

     }

 }

 int main(void)

 {

     while(scanf("%d%d",&n,&r),n+r)

     {

         M=;

         memset(c,,sizeof(c));

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++){

                 scanf("%d",&g[i][j]);

                 g[i][j]++;

                 if(g[i][j]>M) M=g[i][j];

             }

         solve();

         for(int i=r+;i<=n-r;i++)

             for(int j=r+;j<=n-r;j++)

                 printf(j==n-r?"%d \n":"%d ",ans[i][j]-);

     }

     return ;

 }

 /*

 3 1

 1 9 6

 4 5 2

 3 7 8

 5 1

 0 0 1 1 0

 1 0 1 0 1

 0 0 1 1 1

 1 1 1 0 1

 1 0 0 0 1

 */