#include <stdio.h>
#include <stdlib.h>
typedef long long int lli;
#define maxsize 250000
int main(void){
int i,j,n,c,pos,x,y,num,cs,*size,*cnt,*a,**mat,*out,*sz;
lli *s;
size
=(int*)malloc(c
*sizeof(int)); s
=(lli
*)malloc(c
*sizeof(lli
)); cnt
=(int*)malloc((n
+1)*sizeof(int)); a
=(int*)malloc(maxsize
*sizeof(int)); out
=(int*)malloc((n
+1)*sizeof(int)); sz
=(int*)malloc(n
*sizeof(int));
for(i=1;i<=n;i++)cnt[i]=0;
pos=0;
for(i=0;i<c;i++){
s[i]=0;
for(j=0;j<size[i];j++){
s[i]+=x;
cnt[x]++;
a[pos++]=x;}}
mat
=(int**)malloc((n
+1)*sizeof(int*)); for(i
=1;i
<=n
;i
++)mat
[i
]=(int*)malloc(cnt
[i
]*sizeof(int)); for(i=1;i<=n;i++)cnt[i]=0;
pos=0;for(i=0;i<c;i++)for(j=0;j<size[i];j++){x=a[pos];pos++;mat[x][cnt[x]]=i;cnt[x]++;}
for(i=1;i<=n;i++)out[i]=(i==1);
sz[0]=1;num=1;
for(i=0;i<num;i++){
x=sz[i];
for(j=0;j<cnt[x];j++){
cs=mat[x][j];
size[cs]--;
s[cs]-=x;
y=s[cs];
if(size[cs]==1&&out[y]==0){out[y]=1;sz[num++]=y;}}}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgbG9uZyBsb25nIGludCBsbGk7CgojZGVmaW5lIG1heHNpemUgMjUwMDAwCgppbnQgbWFpbih2b2lkKXsKICAgIAogICAgaW50IGksaixuLGMscG9zLHgseSxudW0sY3MsKnNpemUsKmNudCwqYSwqKm1hdCwqb3V0LCpzejsKICAgIGxsaSAqczsKICAgIAogICAgc2NhbmYoIiVkJWQiLCZuLCZjKTsKICAgIHNpemU9KGludCopbWFsbG9jKGMqc2l6ZW9mKGludCkpOwogICAgcz0obGxpKiltYWxsb2MoYypzaXplb2YobGxpKSk7CiAgICBjbnQ9KGludCopbWFsbG9jKChuKzEpKnNpemVvZihpbnQpKTsKICAgIGE9KGludCopbWFsbG9jKG1heHNpemUqc2l6ZW9mKGludCkpOwogICAgb3V0PShpbnQqKW1hbGxvYygobisxKSpzaXplb2YoaW50KSk7CiAgICBzej0oaW50KiltYWxsb2MobipzaXplb2YoaW50KSk7CiAgICAKICAgIGZvcihpPTE7aTw9bjtpKyspY250W2ldPTA7CiAgICAKICAgIHBvcz0wOwogICAgZm9yKGk9MDtpPGM7aSsrKXsKICAgICAgICBzY2FuZigiJWQiLCZzaXplW2ldKTsKCXNbaV09MDsKCWZvcihqPTA7ajxzaXplW2ldO2orKyl7CgkgICAgc2NhbmYoIiVkIiwmeCk7CgkgICAgc1tpXSs9eDsKCSAgICBjbnRbeF0rKzsKCSAgICBhW3BvcysrXT14O319CiAgICAKICAgIG1hdD0oaW50KiopbWFsbG9jKChuKzEpKnNpemVvZihpbnQqKSk7CiAgICBmb3IoaT0xO2k8PW47aSsrKW1hdFtpXT0oaW50KiltYWxsb2MoY250W2ldKnNpemVvZihpbnQpKTsKICAgIGZvcihpPTE7aTw9bjtpKyspY250W2ldPTA7CiAgICBwb3M9MDtmb3IoaT0wO2k8YztpKyspZm9yKGo9MDtqPHNpemVbaV07aisrKXt4PWFbcG9zXTtwb3MrKzttYXRbeF1bY250W3hdXT1pO2NudFt4XSsrO30KICAgIAogICAgZm9yKGk9MTtpPD1uO2krKylvdXRbaV09KGk9PTEpOwogICAgc3pbMF09MTtudW09MTsKICAgIAogICAgZm9yKGk9MDtpPG51bTtpKyspewogICAgICAgIHg9c3pbaV07Cglmb3Ioaj0wO2o8Y250W3hdO2orKyl7CgkgICAgY3M9bWF0W3hdW2pdOwoJICAgIHNpemVbY3NdLS07CgkgICAgc1tjc10tPXg7CgkgICAgeT1zW2NzXTsKCSAgICBpZihzaXplW2NzXT09MSYmb3V0W3ldPT0wKXtvdXRbeV09MTtzeltudW0rK109eTt9fX0KICAgIHByaW50ZigiJWRcbiIsbnVtKTsKICAgIHJldHVybiAwOwp9Cg==