#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stdint.h>
#include<string>
using std::string;
typedef uint8_t U8;
typedef uint16_t U16;
typedef uint32_t U32;
typedef uint64_t U64;
template<typename T>
struct Array{
T*data;
size_t n;
Array(size_t sz=0,int ex=0):data(0),n(0){
resize(sz,ex);
}
void resize(size_t sz,int ex=0);
~Array(){
resize(0);
}
size_t size(){
return n;
}
T&operator[](size_t i){
return data[i];
}
T&operator()(size_t i){
return data[i&(n-1)];
}
}
;
template<typename T>
void Array<T>::resize(size_t sz,int ex){
if(n>0)free((char*)data);
n=0;
if(sz==0)return;
n=sz<<ex;
const size_t nb=128+n*sizeof(T);
data=(T*)calloc(nb,1);
}
typedef enum{
NONE,CONS,CM,ICM,MATCH,AVG,MIX2,MIX,ISSE,SSE}
CompType;
const int compsize[256]={
0,2,3,2,3,4,6,6,3,5}
;
struct ZP{
ZP(){
out=0;
clear();
}
void clear();
void run(U32 input){
pc=hbegin;
a=input;
while(execute());
}
int read(FILE*in2);
FILE*out;
Array<U8>hd,m;
Array<U32>h,r;
int cend,hbegin,hend,f,pc;
U32 a,b,c,d;
void init(int hbits,int mbits);
int execute();
void div(U32 x){
if(x)a/=x;
else a=0;
}
void mod(U32 x){
if(x)a%=x;
else a=0;
}
void swap(U32&x){
a^=x;
x^=a;
a^=x;
}
void swap(U8&x){
a^=x;
x^=a;
a^=x;
}
}
;
int ZP::read(FILE*in2){
int hsize=getc(in2);
hsize+=getc(in2)*256;
hd.resize(hsize+300);
cend=hbegin=hend=0;
hd[cend++]=hsize&255;
hd[cend++]=hsize>>8;
while(cend<7)hd[cend++]=getc(in2);
int n=hd[cend-1];
for(int i=0;i<n;++i){
int type=getc(in2);
hd[cend++]=type;
int size=compsize[type];
for(int j=1;j<size;++j)
hd[cend++]=getc(in2);
}
hd[cend++]=getc(in2);
hbegin=hend=cend+128;
while(hend<hsize+129){
int op=getc(in2);
hd[hend++]=op;
}
hd[hend++]=getc(in2);
return cend+hend-hbegin;
}
void ZP::clear(){
cend=hbegin=hend=0;
hd.resize(0);
a=b=c=d=f=pc=0;
h.resize(0);
m.resize(0);
r.resize(0);
}
void ZP::init(int hbits,int mbits){
a=b=c=d=f=pc=0;
h.resize(1,hbits);
m.resize(1,mbits);
r.resize(256);
}
#define C(i,L,R)\
case i:L(a R);break;\
case i+1:L(b R);break;\
case i+2:L(c R);break;\
case i+3:L(d R);break;\
case i+4:L(U32(m(b))R);break;\
case i+5:L(U32(m(c))R);break;\
case i+6:L(h(d) R);break;\
case i+7:L(U32(hd[pc++])R);break;
#define C1(i,x)\
case i:swap(x);break;\
case i+1:++x;break;\
case i+2:--x;break;\
case i+3:x=~x;break;\
case i+4:x=0;break;
int ZP::execute(){
switch(hd[pc++]){
case 7:a=r[hd[pc++]];break;
case 15:b=r[hd[pc++]];break;
case 23:c=r[hd[pc++]];break;
case 31:d=r[hd[pc++]];break;
case 39:if(f)pc+=((hd[pc]+128)&255)-127;else ++pc;break;
case 47:if(!f)pc+=((hd[pc]+128)&255)-127;else ++pc;break;
case 55:r[hd[pc++]]=a;break;
case 56:return 0;
case 57:if(out)putc(a,out);break;
case 59:a=(a+m(b)+512)*773;break;
case 60:h(d)=(h(d)+a+512)*773;break;
case 63:pc+=((hd[pc]+128)&255)-127;break;
C1(0,a)
C1(8,b)
C1(16,c)
C1(24,d)
C1(32,m(b))
C1(40,m(c))
C1(48,h(d))
C(64,a=,)
C(72,b=,)
C(80,c=,)
C(88,d=,)
C(96,m(b)=,)
C(104,m(c)=,)
C(112,h(d)=,)
C(128,a+=,)
C(136,a-=,)
C(144,a*=,)
C(152,div,)
C(160,mod,)
C(168,a&=,)
C(176,a&= ~,)
C(184,a|=,)
C(192,a^=,)
C(200,a<<=,&31)
C(208,a>>=,&31)
C(216,f=,==a)
C(224,f=,>a)
C(232,f=,<a)
}
return 1;
}
struct CP{
U32 limit,cxt,a,b,c;
Array<U32>cm;
Array<U8>ht;
Array<U16>a16;
void init();
CP(){
init();
}
}
;
void CP::init(){
limit=cxt=a=b=c=0;
cm.resize(0);
ht.resize(0);
a16.resize(0);
}
struct ST{
enum{
N=64}
;
int nns(int n0,int n1);
void ds(int&n0);
void nx(int&n0,int&n1,int y);
U8 ns[1024];
int cminit(int state){
return((ns[state*4+3]*2+1)<<22)/(ns[state*4+2]+ns[state*4+3]+1);
}
ST();
}
;
int ST::nns(int n0,int n1){
const int B=6,bound[B]={
20,48,15,8,6,5}
;
if(n0<n1)return nns(n1,n0);
if(n0<0||n1<0||n1>=B||n0>bound[n1])return 0;
return 1+(n1>0&&n0+n1<=17);
}
void ST::ds(int&n0){
n0=(n0>=1)+(n0>=2)+(n0>=3)+(n0>=4)+(n0>=5)+(n0>=7)+(n0>=8);
}
void ST::nx(int&n0,int&n1,int y){
if(n0<n1)
nx(n1,n0,1-y);
else{
if(y){
++n1;
ds(n0);
}
else{
++n0;
ds(n1);
}
while(!nns(n0,n1)){
if(n1<2)--n0;
else{
n0=(n0*(n1-1)+(n1/2))/n1;
--n1;
}
}
}
}
ST::ST(){
const int N=50;
U8 t[N][N][2]={
{
{
0}
}
}
;
int state=0;
for(int i=0;i<N;++i){
for(int n1=0;n1<=i;++n1){
int n0=i-n1;
int n=nns(n0,n1);
if(n){
t[n0][n1][0]=state;
t[n0][n1][1]=state+n-1;
state+=n;
}
}
}
memset(ns,0,sizeof(ns));
for(int n0=0;n0<N;++n0){
for(int n1=0;n1<N;++n1){
for(int y=0;y<nns(n0,n1);++y){
int s=t[n0][n1][y];
int s0=n0,s1=n1;
nx(s0,s1,0);
ns[s*4+0]=t[s0][s1][0];
s0=n0,s1=n1;
nx(s0,s1,1);
ns[s*4+1]=t[s0][s1][1];
ns[s*4+2]=n0;
ns[s*4+3]=n1;
}
}
}
}
struct PR{
PR(ZP&);
void init();
int predict();
void update(int y);
bool im(){
return z.hd[6]!=0;
}
int c8,hmap4,p[256];
U32 h[256];
ZP&z;
CP comp[256];
int dt2k[256];
int dt[1024];
U16 squasht[4096];
short stretcht[32768];
ST st;
void train(CP&cr,int y){
U32&pn=cr.cm(cr.cxt);
U32 count=pn&0x3ff;
int error=y*32767-(cr.cm(cr.cxt)>>17);
pn+=(error*dt[count]&-1024)+(count<cr.limit);
}
int squash(int x){
return squasht[x+2048];
}
int stretch(int x){
return stretcht[x];
}
int clamp2k(int x){
if(x<-2048)return -2048;
else if(x>2047)return 2047;
else return x;
}
int clamp512k(int x){
if(x<-(1<<19))return -(1<<19);
else if(x>=(1<<19))return(1<<19)-1;
else return x;
}
size_t find(Array<U8>&ht,int sizebits,U32 cxt);
}
;
PR::PR(ZP&zr):
c8(1),hmap4(1),z(zr){
dt2k[0]=0;
for(int i=1;i<256;++i)
dt2k[i]=2048/i;
for(int i=0;i<1024;++i)
dt[i]=(1<<17)/(i*2+3)*2;
for(int i=0;i<32768;++i)
stretcht[i]=int(log((i+0.5)/(32767.5-i))*64+0.5+100000)-100000;
for(int i=0;i<4096;++i)
squasht[i]=int(32768.0/(1+exp((i-2048)*(-1.0/64))));
}
void PR::init(){
z.init(z.hd[2],z.hd[3]);
for(int i=0;i<256;++i)h[i]=p[i]=0;
for(int i=0;i<256;++i)comp[i].init();
int n=z.hd[6];
const U8*cp=&z.hd[7];
for(int i=0;i<n;++i){
CP&cr=comp[i];
switch(cp[0]){
case CONS:
p[i]=(cp[1]-128)*4;
break;
case CM:
cr.cm.resize(1,cp[1]);
cr.limit=cp[2]*4;
for(size_t j=0;j<cr.cm.size();++j)
cr.cm[j]=0x80000000;
break;
case ICM:
cr.limit=1023;
cr.cm.resize(256);
cr.ht.resize(64,cp[1]);
for(size_t j=0;j<cr.cm.size();++j)
cr.cm[j]=st.cminit(j);
break;
case MATCH:
cr.cm.resize(1,cp[1]);
cr.ht.resize(1,cp[2]);
cr.ht(0)=1;
break;
case MIX2:
cr.c=(size_t(1)<<cp[1]);
cr.a16.resize(1,cp[1]);
for(size_t j=0;j<cr.a16.size();++j)
cr.a16[j]=32768;
break;
case MIX:{
int m=cp[3];
cr.c=(size_t(1)<<cp[1]);
cr.cm.resize(m,cp[1]);
for(size_t j=0;j<cr.cm.size();++j)
cr.cm[j]=65536/m;
break;
}
case ISSE:
cr.ht.resize(64,cp[1]);
cr.cm.resize(512);
for(int j=0;j<256;++j){
cr.cm[j*2]=1<<15;
cr.cm[j*2+1]=clamp512k(stretch(st.cminit(j)>>8)<<10);
}
break;
case SSE:
cr.cm.resize(32,cp[1]);
cr.limit=cp[4]*4;
for(size_t j=0;j<cr.cm.size();++j)
cr.cm[j]=squash((j&31)*64-992)<<17|cp[3];
break;
}
cp+=compsize[*cp];
}
}
int PR::predict(){
int n=z.hd[6];
const U8*cp=&z.hd[7];
for(int i=0;i<n;++i){
CP&cr=comp[i];
switch(cp[0]){
case CM:
cr.cxt=h[i]^hmap4;
p[i]=stretch(cr.cm(cr.cxt)>>17);
break;
case ICM:
if(c8==1||(c8&0xf0)==16)cr.c=find(cr.ht,cp[1]+2,h[i]+16*c8);
cr.cxt=cr.ht[cr.c+(hmap4&15)];
p[i]=stretch(cr.cm(cr.cxt)>>8);
break;
case MATCH:
if(cr.a==0)p[i]=0;
else{
cr.c=(cr.ht(cr.limit-cr.b)>>(7-cr.cxt))&1;
p[i]=stretch(dt2k[cr.a]*(cr.c*-2+1)&32767);
}
break;
case AVG:
p[i]=(p[cp[1]]*cp[3]+p[cp[2]]*(256-cp[3]))>>8;
break;
case MIX2:{
cr.cxt=((h[i]+(c8&cp[5]))&(cr.c-1));
int w=cr.a16[cr.cxt];
p[i]=(w*p[cp[2]]+(65536-w)*p[cp[3]])>>16;
}
break;
case MIX:{
int m=cp[3];
cr.cxt=h[i]+(c8&cp[5]);
cr.cxt=(cr.cxt&(cr.c-1))*m;
int*wt=(int*)&cr.cm[cr.cxt];
p[i]=0;
for(int j=0;j<m;++j)
p[i]+=(wt[j]>>8)*p[cp[2]+j];
p[i]=clamp2k(p[i]>>8);
}
break;
case ISSE:{
if(c8==1||(c8&0xf0)==16)
cr.c=find(cr.ht,cp[1]+2,h[i]+16*c8);
cr.cxt=cr.ht[cr.c+(hmap4&15)];
int*wt=(int*)&cr.cm[cr.cxt*2];
p[i]=clamp2k((wt[0]*p[cp[2]]+wt[1]*64)>>16);
}
break;
case SSE:{
cr.cxt=(h[i]+c8)*32;
int pq=p[cp[2]]+992;
if(pq<0)pq=0;
if(pq>1983)pq=1983;
int wt=pq&63;
pq>>=6;
cr.cxt+=pq;
p[i]=stretch(((cr.cm(cr.cxt)>>10)*(64-wt)+(cr.cm(cr.cxt+1)>>10)*wt)
>>13);
cr.cxt+=wt>>5;
}
}
cp+=compsize[cp[0]];
}
return squash(p[n-1]);
}
void PR::update(int y){
const U8*cp=&z.hd[7];
int n=z.hd[6];
for(int i=0;i<n;++i){
CP&cr=comp[i];
switch(cp[0]){
case CM:
train(cr,y);
break;
case ICM:{
cr.ht[cr.c+(hmap4&15)]=st.ns[cr.ht[cr.c+(hmap4&15)]*4+y];
U32&pn=cr.cm(cr.cxt);
pn+=int(y*32767-(pn>>8))>>2;
}
break;
case MATCH:
{
if(int(cr.c)!=y)cr.a=0;
cr.ht(cr.limit)+=cr.ht(cr.limit)+y;
if(++cr.cxt==8){
cr.cxt=0;
++cr.limit;
cr.limit&=(1<<cp[2])-1;
if(cr.a==0){
cr.b=cr.limit-cr.cm(h[i]);
if(cr.b&(cr.ht.size()-1))
while(cr.a<255&&cr.ht(cr.limit-cr.a-1)==cr.ht(cr.limit-cr.a-cr.b-1))
++cr.a;
}
else cr.a+=cr.a<255;
cr.cm(h[i])=cr.limit;
}
}
break;
case MIX2:{
int err=(y*32767-squash(p[i]))*cp[4]>>5;
int w=cr.a16[cr.cxt];
w+=(err*(p[cp[2]]-p[cp[3]])+(1<<12))>>13;
if(w<0)w=0;
if(w>65535)w=65535;
cr.a16[cr.cxt]=w;
}
break;
case MIX:{
int m=cp[3];
int err=(y*32767-squash(p[i]))*cp[4]>>4;
int*wt=(int*)&cr.cm[cr.cxt];
for(int j=0;j<m;++j)
wt[j]=clamp512k(wt[j]+((err*p[cp[2]+j]+(1<<12))>>13));
}
break;
case ISSE:{
int err=y*32767-squash(p[i]);
int*wt=(int*)&cr.cm[cr.cxt*2];
wt[0]=clamp512k(wt[0]+((err*p[cp[2]]+(1<<12))>>13));
wt[1]=clamp512k(wt[1]+((err+16)>>5));
cr.ht[cr.c+(hmap4&15)]=st.ns[cr.cxt*4+y];
}
break;
case SSE:
train(cr,y);
}
cp+=compsize[cp[0]];
}
c8+=c8+y;
if(c8>=256){
z.run(c8-256);
hmap4=1;
c8=1;
for(int i=0;i<n;++i)h[i]=z.h(i);
}
else if(c8>=16&&c8<32)
hmap4=(hmap4&0xf)<<5|y<<4|1;
else
hmap4=(hmap4&0x1f0)|(((hmap4&0xf)*2+y)&0xf);
}
size_t PR::find(Array<U8>&ht,int sizebits,U32 cxt){
int chk=cxt>>sizebits&255;
size_t h0=(cxt*16)&(ht.size()-16);
if(ht[h0]==chk)return h0;
size_t h1=h0^16;
if(ht[h1]==chk)return h1;
size_t h2=h0^32;
if(ht[h2]==chk)return h2;
if(ht[h0+1]<=ht[h1+1]&&ht[h0+1]<=ht[h2+1])
return memset(&ht[h0],0,16),ht[h0]=chk,h0;
else if(ht[h1+1]<ht[h2+1])
return memset(&ht[h1],0,16),ht[h1]=chk,h1;
else
return memset(&ht[h2],0,16),ht[h2]=chk,h2;
}
struct DE{
FILE*in;
DE(ZP&z);
int de();
void init();
U32 low,high;
U32 curr;
PR pr;
int decode(int p);
}
;
DE::DE(ZP&z):
in(0),low(1),high(0xFFFFFFFF),curr(0),pr(z){
}
void DE::init(){
pr.init();
if(pr.im())low=1,high=0xFFFFFFFF,curr=0;
else low=high=curr=0;
}
int DE::decode(int p){
U32 mid=low+U32(((high-low)*U64(U32(p)))>>16);
int y=curr<=mid;
if(y)high=mid;
else low=mid+1;
while((high^low)<0x1000000){
high=high<<8|255;
low=low<<8;
low+=(low==0);
curr=curr<<8|getc(in);
}
return y;
}
int DE::de(){
if(pr.im()){
if(curr==0){
for(int i=0;i<4;++i)
curr=curr<<8|getc(in);
}
if(decode(0)){
return -1;
}
else{
int c=1;
while(c<256){
int p=pr.predict()*2+1;
c+=c+decode(p);
pr.update(c&1);
}
return c-256;
}
}
else{
if(curr==0){
for(int i=0;i<4;++i)
curr=curr<<8|getc(in);
if(curr==0)return -1;
}
--curr;
return getc(in);
}
}
struct PP{
int state;
int hsize;
int ph,pm;
ZP z;
PP():state(0),hsize(0),ph(0),pm(0){
}
void init(int h,int m);
int write(int c);
}
;
void PP::init(int h,int m){
state=hsize=0;
ph=h;
pm=m;
z.clear();
}
int PP::write(int c){
switch(state){
case 0:
state=c+1;
if(state==1)z.clear();
break;
case 1:
if(c>=0&&z.out)putc(c,z.out);
break;
case 2:
hsize=c;
state=3;
break;
case 3:
hsize+=c*256;
z.hd.resize(hsize+300);
z.cend=8;
z.hbegin=z.hend=z.cend+128;
z.hd[4]=ph;
z.hd[5]=pm;
state=4;
break;
case 4:
z.hd[z.hend++]=c;
if(z.hend-z.hbegin==hsize){
hsize=z.cend-2+z.hend-z.hbegin;
z.hd[0]=hsize&255;
z.hd[1]=hsize>>8;
z.init(z.hd[4],z.hd[5]);
state=5;
}
break;
case 5:
z.run(c);
break;
}
return state;
}
struct DC{
DC():z(),dec(z),pp(),ds(0){
}
bool fb();
bool ff(string&);
void de();
ZP z;
DE dec;
PP pp;
int ds;
}
;
bool DC::fb(){
U32 h1=0x3D49B113,h2=0x29EB7F93,h3=0x2614BE13,h4=0x3828EB13;
int c;
while((c=getc(dec.in))!=EOF){
h1=h1*12+c;
h2=h2*20+c;
h3=h3*28+c;
h4=h4*44+c;
if(h1==0xB16B88F1&&h2==0xFF5376F1&&h3==0x72AC5BF1&&h4==0x2F909AF1)
break;
}
if(c<0)return false;
getc(dec.in);
getc(dec.in);
z.read(dec.in);
ds=0;
return true;
}
bool DC::ff(string&filename){
int c=getc(dec.in);
if(c==1){
while(true){
c=getc(dec.in);
if(c==0){
return true;
}
filename+=char(c);
}
}
return false;
}
void DC::de(){
while(getc(dec.in));
getc(dec.in);
if(ds==0){
dec.init();
pp.init(z.hd[4],z.hd[5]);
ds=1;
}
while((pp.state&3)!=1)
pp.write(dec.de());
while(true){
int c=dec.de();
pp.write(c);
if(c==-1)break;
}
if(getc(dec.in)==253){
for(int i=1;i<=20;++i)
getc(dec.in);
}
}
int main(int argc,char**argv){
DC d;
if(argc<2||!(d.dec.in=fopen(argv[1],"rb")))return 0;
string sout;
while(d.fb()){
while(d.ff(sout)){
if(sout!=""){
if(d.pp.z.out)fclose(d.pp.z.out);
d.pp.z.out=fopen(sout.c_str(),"wb");
sout="";
}
d.de();
}
}
return 0;
}