#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<sstream>
#include<string>
#include<string.h>
#include<deque>
#include<vector>
#include<stack>
#include<queue>
#include<math.h>
#include<map>
#include<set>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
double PI = acos(-1);
double EPS = 1e-7;
int INF = 1000000000;
int MAXINT = 2147483647;
LL INFLL = 1000000000000000000LL;
LL MAXLL = 9223372036854775807LL;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define SIZE(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define RESET(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,c) for (int (a)=(b); (a)<=(c); (a)++)
#define FORD(a,b,c) for (int (a)=(b); (a)>=(c); (a)--)
#define FORIT(a,b) for (__typeof((b).begin()) a=(b).begin(); a!=(b).end(); (a)++)
#define MIN(a, b) (a) = min((a), (b))
#define MAX(a, b) (a) = max((a), (b))
#define PAUSE system("pause")
#define input(in) freopen(in,"r",stdin)
#define output(out) freopen(out,"w",stdout)
inline void inp(int &num)
{
bool neg=0;
num=0;
char c;
while ((c=getchar_unlocked()) && (!isdigit(c) && c!='-'));
if (c=='-')
{
neg=1;
c=getchar_unlocked();
}
do num=num*10+c-'0';
while ((c=getchar_unlocked()) && isdigit(c));
num*=(neg)?-1:1;
}
/*\ \
\ \*/
vector<pii> ls[400005];
vector<int> rt[400005];
pair<pii,int> p[100005];
vector<pii> loc[100005];
inline void merge(int id,vector<pii> &res,vector<pii> &a,vector<pii> &b)
{
int la = 0;
int lb = 0;
int sa = SIZE(a);
int sb = SIZE(b);
while(la < sa || lb < sb)
{
if (la >= sa) {res.pb(b[lb]);loc[b[lb].se].pb(mp(id,SIZE(res)-1));lb++;}
else if (lb >= sb) {res.pb(a[la]);loc[a[la].se].pb(mp(id,SIZE(res)-1));la++;}
else
{
if (a[la] < b[lb]) {res.pb(a[la]);loc[a[la].se].pb(mp(id,SIZE(res)-1));la++;}
else {res.pb(b[lb]);loc[b[lb].se].pb(mp(id,SIZE(res)-1));lb++;}
}
}
}
inline void build_x(int n,int l,int r)
{
if (l == r)
{
ls[n].clear();
ls[n].pb(mp(p[l].fi.se,p[l].se));
rt[n].assign(SIZE(ls[n])<<2,0);
loc[p[l].se].pb(mp(n,0));
return;
}
int m = (l+r)>>1;
build_x((n<<1),l,m);
build_x((n<<1)+1,m+1,r);
ls[n].clear();
merge(n,ls[n],ls[(n<<1)],ls[(n<<1)+1]);
rt[n].assign(SIZE(ls[n])<<2,0);
}
inline int query_y(int nx,int n,int l,int r,int ly,int ry)
{
if (ly > ls[nx][r].fi || ry < ls[nx][l].fi) return 0;
if (ly <= ls[nx][l].fi && ls[nx][r].fi <= ry)
{
return rt[nx][n];
}
int res = 0;
int m = (l+r)>>1;
if (ly <= ls[nx][m].fi) MAX(res,query_y(nx,(n<<1),l,m,ly,min(ls[nx][m].fi,ry)));
if (ls[nx][m+1].fi <= ry) MAX(res,query_y(nx,(n<<1)+1,m+1,r,max(ls[nx][m+1].fi,ly),ry));
return res;
}
inline int query_x(int n,int l,int r,int lx,int rx,int ly,int ry)
{
if (lx > p[r].fi.fi || rx < p[l].fi.fi) return 0;
if (lx <= p[l].fi.fi && p[r].fi.fi <= rx)
{
return query_y(n,1,0,SIZE(ls[n])-1,ly,ry);
}
int res = 0;
int m = (l+r)>>1;
if (lx <= p[m].fi.fi) MAX(res,query_x((n<<1),l,m,lx,min(p[m].fi.fi,rx),ly,ry));
if (p[m+1].fi.fi <= rx) MAX(res,query_x((n<<1)+1,m+1,r,max(p[m+1].fi.fi,lx),rx,ly,ry));
return res;
}
inline void update_y(int nx,int n,int l,int r,int fy,int v)
{
if (l == r)
{
MAX(rt[nx][n],v);
return;
}
int m = (l+r)>>1;
if (fy <= m) update_y(nx,(n<<1),l,m,fy,v);
else update_y(nx,(n<<1)+1,m+1,r,fy,v);
rt[nx][n] = max(rt[nx][(n<<1)],rt[nx][(n<<1)+1]);
}
int main()
{
int t;
t=10;
FOR(tc,1,t)
{
int n;
n = 100000;
pair<pair<pii,pii>,int> d[100005];
FOR(a,1,n)
{
d[a].fi.se.fi= 1;
d[a].fi.se.se= 1000000;
d[a].fi.fi.fi= 1000000-a;
d[a].fi.fi.se= 100;
loc[a].clear();
d[a].se = a;
p[a-1] = mp(mp(d[a].fi.se.fi+d[a].fi.se.se,d[a].fi.se.fi-d[a].fi.se.se),a);
}
sort(p,p+n);
sort(d+1,d+n+1);
build_x(1,0,n-1);
int ans = 0;
FOR(a,1,n)
{
int w = d[a].fi.fi.se;
int x = d[a].fi.se.fi;
int y = d[a].fi.se.se;
int id = d[a].se;
int val = query_x(1,0,n-1,x+y-w,x+y+w,x-y-w,x-y+w);
FOR(b,0,SIZE(loc[id])-1)
{
update_y(loc[id][b].fi,1,0,SIZE(ls[loc[id][b].fi])-1,loc[id][b].se,val+1);
}
MAX(ans,val+1);
}
printf("Case %d: %d\n",tc,ans);
}
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPHN0ZGxpYi5oPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPHNzdHJlYW0+CiNpbmNsdWRlPHN0cmluZz4KI2luY2x1ZGU8c3RyaW5nLmg+CiNpbmNsdWRlPGRlcXVlPgojaW5jbHVkZTx2ZWN0b3I+CiNpbmNsdWRlPHN0YWNrPgojaW5jbHVkZTxxdWV1ZT4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPHNldD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBMTDsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHBpaTsKCmRvdWJsZSBQSSA9IGFjb3MoLTEpOwpkb3VibGUgRVBTID0gMWUtNzsKaW50IElORiA9IDEwMDAwMDAwMDA7CmludCBNQVhJTlQgPSAyMTQ3NDgzNjQ3OwpMTCBJTkZMTCA9IDEwMDAwMDAwMDAwMDAwMDAwMDBMTDsKTEwgTUFYTEwgPSA5MjIzMzcyMDM2ODU0Nzc1ODA3TEw7CgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCgojZGVmaW5lIFNJWkUoYSkgKGludClhLnNpemUoKQojZGVmaW5lIEFMTChhKSBhLmJlZ2luKCksYS5lbmQoKQojZGVmaW5lIFJFU0VUKGEsYikgbWVtc2V0KGEsYixzaXplb2YoYSkpCiNkZWZpbmUgRk9SKGEsYixjKSBmb3IgKGludCAoYSk9KGIpOyAoYSk8PShjKTsgKGEpKyspCiNkZWZpbmUgRk9SRChhLGIsYykgZm9yIChpbnQgKGEpPShiKTsgKGEpPj0oYyk7IChhKS0tKQojZGVmaW5lIEZPUklUKGEsYikgZm9yIChfX3R5cGVvZigoYikuYmVnaW4oKSkgYT0oYikuYmVnaW4oKTsgYSE9KGIpLmVuZCgpOyAoYSkrKykKI2RlZmluZSBNSU4oYSwgYikgKGEpID0gbWluKChhKSwgKGIpKQojZGVmaW5lIE1BWChhLCBiKSAoYSkgPSBtYXgoKGEpLCAoYikpCiNkZWZpbmUgUEFVU0Ugc3lzdGVtKCJwYXVzZSIpCgojZGVmaW5lIGlucHV0KGluKSBmcmVvcGVuKGluLCJyIixzdGRpbikKI2RlZmluZSBvdXRwdXQob3V0KSBmcmVvcGVuKG91dCwidyIsc3Rkb3V0KQoKaW5saW5lIHZvaWQgaW5wKGludCAmbnVtKQp7Cglib29sIG5lZz0wOwoJbnVtPTA7CgljaGFyIGM7Cgl3aGlsZSAoKGM9Z2V0Y2hhcl91bmxvY2tlZCgpKSAmJiAoIWlzZGlnaXQoYykgJiYgYyE9Jy0nKSk7CglpZiAoYz09Jy0nKQoJewoJCW5lZz0xOwoJCWM9Z2V0Y2hhcl91bmxvY2tlZCgpOwoJfQoJZG8gbnVtPW51bSoxMCtjLScwJzsKCXdoaWxlICgoYz1nZXRjaGFyX3VubG9ja2VkKCkpICYmIGlzZGlnaXQoYykpOwoJbnVtKj0obmVnKT8tMToxOwp9IAoKLypcICAgXApcICAgXCovCgoKCnZlY3RvcjxwaWk+IGxzWzQwMDAwNV07CnZlY3RvcjxpbnQ+IHJ0WzQwMDAwNV07CnBhaXI8cGlpLGludD4gcFsxMDAwMDVdOwoKdmVjdG9yPHBpaT4gbG9jWzEwMDAwNV07CgppbmxpbmUgdm9pZCBtZXJnZShpbnQgaWQsdmVjdG9yPHBpaT4gJnJlcyx2ZWN0b3I8cGlpPiAmYSx2ZWN0b3I8cGlpPiAmYikKewoJaW50IGxhID0gMDsKCWludCBsYiA9IDA7CglpbnQgc2EgPSBTSVpFKGEpOwoJaW50IHNiID0gU0laRShiKTsKCXdoaWxlKGxhIDwgc2EgfHwgbGIgPCBzYikKCXsKCQlpZiAobGEgPj0gc2EpIHtyZXMucGIoYltsYl0pO2xvY1tiW2xiXS5zZV0ucGIobXAoaWQsU0laRShyZXMpLTEpKTtsYisrO30KCQllbHNlIGlmIChsYiA+PSBzYikge3Jlcy5wYihhW2xhXSk7bG9jW2FbbGFdLnNlXS5wYihtcChpZCxTSVpFKHJlcyktMSkpO2xhKys7fQoJCWVsc2UKCQl7CgkJCWlmIChhW2xhXSA8IGJbbGJdKSB7cmVzLnBiKGFbbGFdKTtsb2NbYVtsYV0uc2VdLnBiKG1wKGlkLFNJWkUocmVzKS0xKSk7bGErKzt9CgkJCWVsc2Uge3Jlcy5wYihiW2xiXSk7bG9jW2JbbGJdLnNlXS5wYihtcChpZCxTSVpFKHJlcyktMSkpO2xiKys7fQoJCX0KCX0KfQoKCmlubGluZSB2b2lkIGJ1aWxkX3goaW50IG4saW50IGwsaW50IHIpCnsKCWlmIChsID09IHIpCgl7CgkJbHNbbl0uY2xlYXIoKTsKCQlsc1tuXS5wYihtcChwW2xdLmZpLnNlLHBbbF0uc2UpKTsKCQlydFtuXS5hc3NpZ24oU0laRShsc1tuXSk8PDIsMCk7CgkJbG9jW3BbbF0uc2VdLnBiKG1wKG4sMCkpOwoJCXJldHVybjsKCX0KCWludCBtID0gKGwrcik+PjE7CglidWlsZF94KChuPDwxKSxsLG0pOwoJYnVpbGRfeCgobjw8MSkrMSxtKzEscik7Cglsc1tuXS5jbGVhcigpOwoJbWVyZ2Uobixsc1tuXSxsc1sobjw8MSldLGxzWyhuPDwxKSsxXSk7CglydFtuXS5hc3NpZ24oU0laRShsc1tuXSk8PDIsMCk7Cn0KCmlubGluZSBpbnQgcXVlcnlfeShpbnQgbngsaW50IG4saW50IGwsaW50IHIsaW50IGx5LGludCByeSkKewoJaWYgKGx5ID4gbHNbbnhdW3JdLmZpIHx8IHJ5IDwgbHNbbnhdW2xdLmZpKSByZXR1cm4gMDsKCWlmIChseSA8PSBsc1tueF1bbF0uZmkgJiYgbHNbbnhdW3JdLmZpIDw9IHJ5KQoJewoJCXJldHVybiBydFtueF1bbl07Cgl9CglpbnQgcmVzID0gMDsKCWludCBtID0gKGwrcik+PjE7CglpZiAobHkgPD0gbHNbbnhdW21dLmZpKSBNQVgocmVzLHF1ZXJ5X3kobngsKG48PDEpLGwsbSxseSxtaW4obHNbbnhdW21dLmZpLHJ5KSkpOwoJaWYgKGxzW254XVttKzFdLmZpIDw9IHJ5KSBNQVgocmVzLHF1ZXJ5X3kobngsKG48PDEpKzEsbSsxLHIsbWF4KGxzW254XVttKzFdLmZpLGx5KSxyeSkpOwoJcmV0dXJuIHJlczsKfQoKCmlubGluZSBpbnQgcXVlcnlfeChpbnQgbixpbnQgbCxpbnQgcixpbnQgbHgsaW50IHJ4LGludCBseSxpbnQgcnkpCnsKCWlmIChseCA+IHBbcl0uZmkuZmkgfHwgcnggPCBwW2xdLmZpLmZpKSByZXR1cm4gMDsKCWlmIChseCA8PSBwW2xdLmZpLmZpICYmIHBbcl0uZmkuZmkgPD0gcngpCgl7CgkJcmV0dXJuIHF1ZXJ5X3kobiwxLDAsU0laRShsc1tuXSktMSxseSxyeSk7Cgl9CglpbnQgcmVzID0gMDsKCWludCBtID0gKGwrcik+PjE7CglpZiAobHggPD0gcFttXS5maS5maSkgTUFYKHJlcyxxdWVyeV94KChuPDwxKSxsLG0sbHgsbWluKHBbbV0uZmkuZmkscngpLGx5LHJ5KSk7CglpZiAocFttKzFdLmZpLmZpIDw9IHJ4KSBNQVgocmVzLHF1ZXJ5X3goKG48PDEpKzEsbSsxLHIsbWF4KHBbbSsxXS5maS5maSxseCkscngsbHkscnkpKTsKCXJldHVybiByZXM7Cn0KCgppbmxpbmUgdm9pZCB1cGRhdGVfeShpbnQgbngsaW50IG4saW50IGwsaW50IHIsaW50IGZ5LGludCB2KQp7CglpZiAobCA9PSByKQoJewoJCU1BWChydFtueF1bbl0sdik7CgkJcmV0dXJuOwoJfQoJaW50IG0gPSAobCtyKT4+MTsKCWlmIChmeSA8PSBtKSB1cGRhdGVfeShueCwobjw8MSksbCxtLGZ5LHYpOwoJZWxzZSB1cGRhdGVfeShueCwobjw8MSkrMSxtKzEscixmeSx2KTsKCXJ0W254XVtuXSA9IG1heChydFtueF1bKG48PDEpXSxydFtueF1bKG48PDEpKzFdKTsKfQoKaW50IG1haW4oKQp7CglpbnQgdDsKCXQ9MTA7CglGT1IodGMsMSx0KQoJewoJCWludCBuOwoJCW4gPSAxMDAwMDA7CgkJcGFpcjxwYWlyPHBpaSxwaWk+LGludD4gZFsxMDAwMDVdOwoJCUZPUihhLDEsbikKCQl7CgkJCWRbYV0uZmkuc2UuZmk9IDE7CgkJCWRbYV0uZmkuc2Uuc2U9IDEwMDAwMDA7CgkJCWRbYV0uZmkuZmkuZmk9IDEwMDAwMDAtYTsKCQkJZFthXS5maS5maS5zZT0gMTAwOwoJCQkKCQkJbG9jW2FdLmNsZWFyKCk7CgkJCWRbYV0uc2UgPSBhOwoJCQlwW2EtMV0gPSBtcChtcChkW2FdLmZpLnNlLmZpK2RbYV0uZmkuc2Uuc2UsZFthXS5maS5zZS5maS1kW2FdLmZpLnNlLnNlKSxhKTsKCQl9CgoJCXNvcnQocCxwK24pOwoJCXNvcnQoZCsxLGQrbisxKTsKCgkJYnVpbGRfeCgxLDAsbi0xKTsKCQkKCQkKCQlpbnQgYW5zID0gMDsKCQlGT1IoYSwxLG4pCgkJewoJCQlpbnQgdyA9IGRbYV0uZmkuZmkuc2U7CgkJCWludCB4ID0gZFthXS5maS5zZS5maTsKCQkJaW50IHkgPSBkW2FdLmZpLnNlLnNlOwoJCQlpbnQgaWQgPSBkW2FdLnNlOwoJCQlpbnQgdmFsID0gcXVlcnlfeCgxLDAsbi0xLHgreS13LHgreSt3LHgteS13LHgteSt3KTsKCQkJRk9SKGIsMCxTSVpFKGxvY1tpZF0pLTEpCgkJCXsKCQkJCXVwZGF0ZV95KGxvY1tpZF1bYl0uZmksMSwwLFNJWkUobHNbbG9jW2lkXVtiXS5maV0pLTEsbG9jW2lkXVtiXS5zZSx2YWwrMSk7CgkJCX0KCQkJTUFYKGFucyx2YWwrMSk7CgkJfQoJCXByaW50ZigiQ2FzZSAlZDogJWRcbiIsdGMsYW5zKTsKCX0KfQ==