Драган е успешен информатичар кој пред некое време отворил своја фирма. Даше е негов богат познаник кој веднаш после него отворил своја фирма. Прво Драган вработил еден човек - Х. И Даше вработил еден човек - Y. Потоа Драган вработил неколкумина, како помошници на Х, на кои X им станал надреден. И Даше вработил исто толкумина на кои Y им станал надреден. И се така, во даден момент, на некој од вработените Драган му вработувал помошници (еден или повеќе) на кои тој вработен им станувал надреден. И Даше веднаш, за идентичниот вработен вработувал исто толку помошници. Така во моментов и двете фирми имаат комплетно иста организациска структура од по N вработени (со јасно дефиниран надреден за секој вработен, освен за првовработениот X, т.е. Y). За секој вработен во двете фирми се знае платата која ја зема во моментот.

Двете фирми се купени од голема компанија која го вовела следното правило:

- На секој нов проект се ангажираат С вработени (од една од компаниите), и тоа точно некој вработен V, па неговиот надреден, па надредениот на надредениот и така нагоре во хиерархијата до вкупно C вработени.
- По завршување на проектот, ангажираните вработени добиваат зголeмување на плата и притоа: најнискиот во хиерархијата (вработениот V) добива зголемување P, а секој од надредените кои биле ангажирани на проектот ќе добијат зголемување толку колку што е вкупното зголемување на двајцата под нив од хиерархијата кои учествувале во проектот). На пример ако А е надреден нa B, B е надреден на С, а C е надреден на D и точно тие учествувале во проектот, тогаш D ќе добие покачување P, C ќе добие покачување колку двајцата под него заедно т.е. колку D (бидејќи под D нема друг учесник во проектот), а тоа е повторно Р, но B ќе добие колку С и D заедно, т.е. 2*Р, а A ќе добие колку B и С заедно, а тоа е 3*P.

Ако на влез ви е дадена структурата на двете фирми (истата), моменталните плати на сите вработени и листа на Q проекти со соодветните податоци, ваша задача е по завршувањето на секој проект и соодветното зголемување на платите, да извршите проверка дали се изедначиле платите во двете фирми (по модул U) за секој пар на соодветни вработени.

Влез

Во првиот ред од влезот ви се дадени три цели броеви N (1 ≤ N ≤ 200 000), Q (2 ≤ Q ≤ 200 000) и U (1 ≤ U ≤ 10⁹).
Во вториот ред ви се дадени N-1 цели броеви, M₂, M₃, … M_n: каде M_i (1 ≤ M_i ≤ N) го претставува индексот на надредениот на вработениот i. Во двете фирми првовработените се означени со индекс 1, а на останатите им е доделен меѓусебно различен индекс по случаен избор.

Во третиот ред ви се дадени N цели броеви – i-тиот број ја претставува платата на вработениот i од фирма 1 пред воведување на новото правило за раст.
Во четвртиот ред ви се дадени N цели броеви – i-тиот број ја претставува платата на вработениот i од фирма 2 пред воведување на новото правило за раст.
Вредностите на иницијалните плати се позитивни цели броеви помали од U;

Во секој од наредните Q редови се дадени по 4 цели броеви F_i (1 ≤ F_i ≤ 2), V_i (1 ≤ V_i ≤ N) , C_i (1 ≤ C_i ≤ N), P_i (1 ≤ P_i < U), кои што означуваат дека вработениот V_i од фирмата F_i започнал проект на кој што работеле C_i вработени, за кој што платата на V_i се зголемила за P_i. Се гарантира дека според описот на задачата ќе постојат C_i вработени кои ќе работат на проектот i.

Излез

Во првиот ред отпечатете Q знаци 1 или 0, i-тиот знак е 1 доколку после изработка на i-тиот проект платите на вработените од двете фирми се идентични по модул U, а нула во спротивно.
Објаснување: А и В се идентични по модул U ако А%U == B%U.

За 25% од поените ќе важи: N,Q <= 1000.
За дополнителни 25% од поените надредениот на вработениот со индекс i е вработен со индекс i-1.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
6 5 7
1 2 3 2 5
4 2 5 6 2 4
6 5 6 3 1 3
1 3 3 4
2 6 3 2
2 4 4 3
1 6 4 1
2 2 2 1

излез
00010

Објаснување:
Проект 1: 1 3 3 4
Фирма 1; вработен 3; учествуваат 3ца: 3, 2 и 1; зголемувањата на плати изнесуваат 4, 4 и 8 соодветно. Платите на сите вработени од оваа фирма после проектот: 4 2 5 6 2 4 -> 12 6 9 6 2 4. Вработените со реден број 1 имаат плати 12 и 6 соодветно – при што 6%7 != 12%7 па се печати 0!

Проект 2: 2 6 3 2
Фирма 2; вработен 6; учествуваат 3ца: 6, 5 и 2; зголемувањата на плати изнесуваат 2, 2 и 4 соодветно. Платите на сите вработени од оваа фирма после проектот: 6 5 6 3 1 3 -> 6 9 6 3 3 5. Вработените со реден број 1 имаат плати 12 и 6 соодветно – при што 6%7 != 12%7 па се печати 0!

Проект 3: 2 4 4 3
Фирма 2; вработен 4; учествуваат 4ца: 4, 3, 2 и 1; зголемувањата на плати изнесуваат 3, 3, 6 и 9 соодветно. Платите на сите вработени од оваа фирма после проектот: 6 9 6 3 3 5 -> 15 15 9 6 3 5. Вработените со реден број 1 имаат плати 12 и 15 соодветно – при што 15%7 != 12%7 па се печати 0!

Проект 4: 1 6 4 1
Фирма 1; вработен 6; учествуваат 4ца: 6, 5, 2 и 1; зголемувањата на плати изнесуваат 1, 1, 2 и 3 соодветно. Платите на сите вработени од оваа фирма после проектот: 12 6 9 6 2 4 -> 15 8 9 6 3 5. Платите на вработените од двете фирми се 15 15 9 6 3 5 и 15 8 9 6 3 5, кои што се идентични по модул 7 ( 15%7 == 8%7 ), па се печати 1!

Проект 5: 2 2 2 1
Фирма 2; вработен 2; учествуваат 2ца: 2 и 1; зголемувањата на плати изнесуваат 1 и 1 соодветно. Платите на сите вработени од оваа фирма после проектот: 15 15 9 6 3 5 -> 16 16 9 6 3 5. Вработените со реден број 1 имаат плати 15 и 16 соодветно – при што 15%7 != 16%7 па се печати 0!