#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <istream> #include <string> #include <queue> #include <deque> #include <random> #include <stack> #include <set> #include <string.h> #include <map> #include <unordered_map> #include <sstream> #include <bitset> #include <fstream> #include <climits> #include <time.h> #include <cassert> using namespace std; #define int long long const int MAXN=100010,N=20010; struct Edge{int v,nx;}edge[MAXN];int h[MAXN],CNT;void init(){memset(h,-1,sizeof(h));CNT=0;}; void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;} int n,m,T,w[MAXN],v[MAXN],cnt,d[MAXN],s[MAXN],o[MAXN]; void dfn(int now){ d[now]=++cnt;o[cnt]=now; for(int i=h[now];i!=-1;i=edge[i].nx){ dfn(edge[i].v); } s[now]=cnt; } struct asking{ int id,l,r; }q[MAXN],nq[MAXN],tl[MAXN],tr[MAXN]; bool cmp(asking x,asking y){if(x.l!=y.l)return x.l<y.l;else return x.r>y.r;} unsigned long long f[20][N]; unsigned long long as1[MAXN],as3[MAXN]; void fz(int l,int r,int lr,int tp){ // cout<<l<<" "<<r<<" "<<lr<<":"<<endl; int cn=0,cl=0,cr=0; int mid=(l+r)>>1; for(int i=1;i<=lr;i++){ if(q[i].r>mid&&q[i].l>mid){ tr[++cr]=q[i]; } else if(q[i].l<mid&&q[i].r<=mid){ tl[++cl]=q[i]; } else{ nq[++cn]=q[i]; } } int ln=l,rn=r; for(int i=1;i<=cn;i++){ // cout<<" "<<nq[i].id<<" "<<nq[i].l<<" "<<nq[i].r<<endl; while(ln<nq[i].l){ for(int j=m;j>=v[ln];j--){ f[tp][j]=max(f[tp][j],f[tp][j-v[o[ln]]]+w[o[ln]]); } ln++; } while(rn>nq[i].r){ for(int j=m;j>=v[rn];j--){ f[tp][j]=max(f[tp][j],f[tp][j-v[o[rn]]]+w[o[rn]]); } rn--; } for(int j=0;j<=m;j++){ //cout<<nq[i].id<<" "<<f[tp][j]<<endl; as1[nq[i].id]^=f[tp][j]*(unsigned long long)(j+1); as3[nq[i].id]^=f[tp][j]*(unsigned long long)(j+1)*(unsigned long long)(j+1)*(unsigned long long)(j+1); } } while(ln<=rn){ for(int j=m;j>=v[rn];j--){ f[tp][j]=max(f[tp][j],f[tp][j-v[o[rn]]]+w[o[rn]]); } rn--; } for(int i=1;i<=cl;i++){ q[i]=tl[i]; } if(l!=r)fz(l,mid,cl,tp+1); for(int i=1;i<=cr;i++){ q[i]=tr[i]; } if(l!=r)fz(mid+1,r,cr,tp+1); } signed main(){init(); scanf("%lld%lld%lld",&n,&m,&T); for(int i=1;i<=n;i++){ scanf("%lld",&v[i]); } for(int i=1;i<=n;i++){ scanf("%lld",&w[i]); } for(int i=2;i<=n;i++){ int fa; scanf("%lld",&fa); add_side(fa,i); } dfn(1); for(int i=2;i<=n;i++){ q[i-1].l=d[i];q[i-1].r=s[i];q[i-1].id=i; } sort(q+1,q+n,cmp); fz(1,n,n-1,0); for(int i=2;i<=n;i++){ printf("%llu %llu\n",as1[i],as3[i]); } return 0; }