#include<cstdio>
#include<memory>
#include<algorithm>
#include <string.h>
using namespace std;
#define __int64 long long
const unsigned int pm=503, pn=8388608;
char fn[96];
unsigned char a[20], b[20];
unsigned int c[pn], h, i, j, k, l, m, n, t;
unsigned long long o;
unsigned __int64 ui, vi, ans[32], u[pn], v[pn];
FILE *ou[pm], *in;
#ifndef MODR
#define MODR 0
#endif
unsigned __int64 add(unsigned __int64 x, unsigned __int64 y)
{
    if(MODR==0)return x+y;
    if((-MODR)-x>y)return x+y;
    return x+y+MODR;
}
void pr(unsigned int f, unsigned __int64 v)
{
        fwrite(&v, sizeof(unsigned __int64), 1, ou[f]);
}
void pri(unsigned __int64 v)
{
        fwrite(&v, sizeof(unsigned __int64), 1, in);
}
void sc(unsigned int f, unsigned __int64 &v)
{
        if(fread(&v, sizeof(unsigned __int64), 1, ou[f])!=1)v=0ull;
}
void sci(unsigned __int64 &v)
{
        if(fread(&v, sizeof(unsigned __int64), 1, in)!=1)v=0ull;
}
unsigned __int64 id(unsigned char a[])
{
        unsigned char c[16], i, j;
        unsigned __int64 s;
        memset(c, 0, 16);
        for(i=0; i<l; i++)
        {
                j=a[i];
                if(j>1)
                        if(c[j])
                        {
                                a[c[j]-1]=i-c[j]+2;
                                a[i]=0;
                        }
                        else c[j]=i+1;
        }
        s=0;
        for(i=0; i<l; i++)
                s=s*(l+1-i)+a[i];
        return s;
}
void ar(unsigned __int64 x)
{
        unsigned char i, j, k;
        k=2;
        for(i=l+1; i; )
        {
                i--;
                j=l-i+1;
                a[i]=char(x%j);
                x/=j;
                if(a[i]>1)
                {
                        a[i+a[i]-1]=k;
                        a[i]=k++;
                }
        }
}
void ad(unsigned __int64 x)
{
        unsigned __int64 s;
        s=id(b);
        pr(s%pm, s);
        pr(s%pm, x);
        o++;
}
unsigned int d(unsigned int x)
{
        unsigned int i;
        for(i=1;; i++)
                if(i!=x&&a[i]==a[x])return i;
}
void c1(unsigned int x)
{
        unsigned int i, j;
        if(a[x]==1)return;
        memcpy(b, &a[1], l);
        if(a[x]==a[0])
        {
                j=h/m+2;
                b[x-1]=1;
                for(i=0; i<l; i++)
                        if(h+i+1<j*m&&b[i]!=1||h+i+2>j*m&&b[i]!=0)break;
                if(i>=l)ans[j]=add(ans[j], vi);
                return;
        }
        if(!a[x])b[x-1]=a[0];
        else
        {
                b[x-1]=1;
                b[d(x)-1]=a[0];
        }
        ad(vi);
}
void c2(unsigned int x, unsigned int y)
{
        unsigned int i, j;
        if(a[x]==1||a[y]==1)return;
        memcpy(b, &a[1], l);
        if(a[x]&&a[x]==a[y])
        {
                j=h/m+2;
                b[x-1]=1;
                b[y-1]=1;
                for(i=0; i<l; i++)
                        if(h+i+1<j*m&&b[i]!=1||h+i+2>j*m&&b[i]!=0)break;
                if(i>=l)ans[j]=add(ans[j], vi);
                return;
        }
        if(a[x])
        {
                b[x-1]=1;
                b[y-1]=1;
                if(a[y])b[d(y)-1]=a[x];
                else b[y-1]=a[x];
        }
        else
                if(a[y])
                {
                        b[x-1]=a[y];
                        b[y-1]=1;
                }
                else
                {
                        b[x-1]=15;
                        b[y-1]=15;
                }
        ad(vi);
}
bool cmp(unsigned int i, unsigned int j)
{
        return u[i]<u[j];
}
int main()
{
        scanf("%d%d", &n, &m);
        //n=10;
        //m=8;
        l=m+m+1;
        b[m+1]=2;
        b[m+m]=2;
        vi=id(b);
        for(i=0; i<pm; i++)
        {
                sprintf(fn, "sa/%04d.dat", i);
                ou[i]=fopen(fn, "wb");
                if(vi%pm==i)
                {
                        pr(i, vi);
                        pr(i, 1);
                }
                fclose(ou[i]);
        }
        for(h=1; h<n*m-m; h++)
        {
                o=0;
                j=h%m;
                for(i=0; i<pm; i++)
                {
                        sprintf(fn, "sb/%04d.dat", i);
                        ou[i]=fopen(fn, "wb");
                }
                for(i=0; i<pm; i++)
                {
                        sprintf(fn, "sa/%04d.dat", i);
                        in=fopen(fn, "rb");
                        while(1)
                        {
                                sci(ui);
                                if(!ui)break;
                                sci(vi);
                                ar(ui);
                                if(a[0]==1)
                                {
                                        memcpy(b, &a[1], l);
                                        ad(vi);
                                        continue;
                                }
                                if(a[0]>1)
                                {
                                        if(j>1)c1(m-2);
                                        if(j&&h/m<n-2)c1(m+m-1);
                                        if(j<m-1&&h/m<n-2)c1(m+m+1);
                                        if(j<m-2)c1(m+2);
                                        continue;
                                }
                                if(j>1)
                                {
                                        if(h/m<n-2)c2(m-2, m+m-1);
                                        if(j<m-1&&h/m<n-2)c2(m-2, m+m+1);
                                        if(j<m-2)c2(m-2, m+2);
                                }
                                if(j&&h/m<n-2)
                                {
                                        if(j<m-1)c2(m+m-1, m+m+1);
                                        if(j<m-2)c2(m+m-1, m+2);
                                }
                                if(j<m-2&&h/m<n-2)c2(m+m+1, m+2);
                        }
                        fclose(in);
                        in=fopen(fn, "wb");
                        fclose(in);
//                        printf("%c%c%c%d", 8, 8, 8, i);
                }
//                printf(" ");
                for(i=0; i<pm; i++)
                {
                        fclose(ou[i]);
                }
                for(i=0; i<pm; i++)
                {
                        sprintf(fn, "sb/%04d.dat", i);
                        ou[i]=fopen(fn, "rb");
                        t=0;
                        while(1)
                        {
                                sc(i, ui);
                                if(!ui)break;
                                u[t]=ui;
                                sc(i, v[t]);
                                c[t]=t++;
                        }
                        fclose(ou[i]);
                        sprintf(fn, "sb/%04d.dat", i);
                        ou[i]=fopen(fn, "wb");
                        fclose(ou[i]);
                        sort(c, c+t, cmp);
                        sprintf(fn, "sa/%04d.dat", i);
                        in=fopen(fn, "wb");
                        vi=v[c[0]];
                        for(k=1; k<=t; k++)
                                if(k<t&&u[c[k]]==u[c[k-1]])vi=add(vi, v[c[k]]);
                                else
                                {
                                        pri(u[c[k-1]]);
                                        pri(vi);
                                        if(k<t)vi=v[c[k]];
                                }
                        fclose(in);
                //        printf("%03d%c%c%c", i, 8, 8, 8);
                }
//                printf("%c%d %d: %llu\n", 13, h/m, j, o);
                if(j>m-2){printf("%llu\n", ans[h/m+2]); fflush(stdout); }
        }
//        scanf("%d", &h);
        return 0;
}