LCA Probleminə Yenidən Baxış
Verilmiş asılmış ağac n (1 ≤ n ≤ 100000) zirvədən ibarətdir və zirvələr 0-dan n-1-ə qədər nömrələnmişdir. Sizdən m (1 ≤ m ≤ 10000000) sorğu üçün iki zirvənin ən kiçik ümumi əcdadını tapmaq tələb olunur.
Sorğular aşağıdakı qaydada yaradılır. Verilmiş a_1, a_2 və x, y, z ədədləri əsasında a_3, ..., a_2m ədədləri belə hesablanır: ai = (x·a_{i-2}+y·a_{i-1}+z) mod n. İlk sorğu < a_1, a_2 > şəklindədir. Əgər i-1-ci sorğunun cavabı v olarsa, i-ci sorğu < (a_{2i-1} + v) mod n, a_2i > şəklindədir.
Giriş verilənləri
Birinci sətir iki ədəd ehtiva edir: n və m. Ağacın kökü 0 nömrəlidir. İkinci sətir n-1 tam ədəd ehtiva edir, burada i-ci ədəd i zirvəsinin əcdadının nömrəsini göstərir. Üçüncü sətir 0-dan n-1-ə qədər iki tam ədəd ehtiva edir: a_1 və a_2. Dördüncü sətir üç tam ədəd ehtiva edir: x, y və z, bu ədədlər mənfi deyil və 10^9-dan böyük deyil.
Çıxış verilənləri
Bütün sorğuların cavabları olan zirvələrin nömrələrinin cəmini çıxarın.