// // main.cpp // 抗体(antibody) // // Created by Y2y7m on 2023/12/7. // Copyright © 2023年 Slip. All rights reserved. // #include <iostream> #include <vector> #include <algorithm> using namespace std; #define int long long #define ull unsigned long long const int maxn=1e5+10,maxm=2e4+10; int n,m,T; int w[maxn],v[maxn]; vector<int> edge[maxn]; int dfn[maxn],tot,sz[maxn]; int id[maxn]; void dfs(int u) { dfn[u]=++tot,sz[u]=1,id[tot]=u; for(int i=0;i<edge[u].size();i++) { int v=edge[u][i]; dfs(v); sz[u]+=sz[v]; } } struct node { int l,r; int id; }; bool cmp(node x,node y) { return x.l<y.l; } int f[maxm]; ull ans1[maxn],ans2[maxn]; void sol(int l,int r,vector<node> query) { if(l>r) return ; if(query.empty()) return ; if(l==r) { node tmp=query[0]; ull t=0; for(int i=0;i<=m;i++) t^=1ull*f[i]*1ull*(i+1); ans1[tmp.id]=t; t=0; for(int i=0;i<=m;i++) t^=1ull*f[i]*1ull*(i+1)*1ull*(i+1)*1ull*(i+1); ans2[tmp.id]=t; return ; } int mid=(l+r)>>1; vector<int> save; for(int i=0;i<=m;i++) save.push_back(f[i]); vector<node> t; for(node x:query) if(x.r<=mid) t.push_back(x); for(int i=mid+1;i<=r;i++) for(int j=m;j>=w[id[i]];j--) f[j]=max(f[j],f[j-w[id[i]]]+v[id[i]]); sol(l,mid,t); for(int i=0;i<=m;i++) f[i]=save[i]; for(int i=l;i<=mid;i++) for(int j=m;j>=w[id[i]];j--) f[j]=max(f[j],f[j-w[id[i]]]+v[id[i]]); t.clear(); for(node x:query) if(x.l>mid) t.push_back(x); sol(mid+1,r,t); t.clear(); for(int i=0;i<=m;i++) f[i]=save[i]; for(node x:query) if(x.l<=mid&&x.r>mid) t.push_back(x); int lpos=l,rpos=r; for(node x:t) { while(lpos<x.l) { for(int j=m;j>=w[id[lpos]];j--) f[j]=max(f[j],f[j-w[id[lpos]]]+v[id[lpos]]); lpos++; } while(rpos>x.r) { for(int j=m;j>=w[id[rpos]];j--) f[j]=max(f[j],f[j-w[id[rpos]]]+v[id[rpos]]); rpos--; } ull t=0; for(int i=0;i<=m;i++) t^=1ull*f[i]*(i+1); ans1[x.id]=t; t=0; for(int i=0;i<=m;i++) t^=1ull*f[i]*1ull*(i+1)*1ull*(i+1)*1ull*(i+1); ans2[x.id]=t; } for(int i=0;i<=m;i++) f[i]=save[i]; } signed main() { scanf("%lld%lld%lld",&n,&m,&T); for(int i=1;i<=n;i++) scanf("%lld",&w[i]); for(int i=1;i<=n;i++) scanf("%lld",&v[i]); int x; for(int i=2;i<=n;i++) { scanf("%lld",&x); edge[x].push_back(i); } dfs(1); vector<node> ask; for(int i=2;i<=n;i++) ask.push_back({dfn[i],dfn[i]+sz[i]-1,i}); sort(ask.begin(),ask.end(),cmp); sol(1,n,ask); for(int i=2;i<=n;i++) printf("%lld %lld\n",ans1[i],ans2[i]); return 0; } /* 3 3 0 1 1 1 1 1 1 1 2 */