Ümumi əcdad - 2
Verilmiş asılmış ağac n (1 ≤ n ≤ 10^5) zirvələrindən ibarətdir və zirvələr 0-dan n - 1-ə qədər nömrələnmişdir. m (1 ≤ m ≤ 10^7) sorğusu üçün iki zirvənin ən kiçik ümumi əcdadını tapmaq lazımdır.
Sorğular aşağıdakı qaydada yaradılır. a[1], a[2] və x, y, z ədədləri verilir. a[3], ..., a[2m] ədədləri isə belə hesablanır:
a[i] = (x * a[i-2] + y * a[i-1] + z) mod n.
Birinci sorğu <a[1], a[2]> şəklindədir. Əgər (i - 1)-ci sorğunun cavabı v-yə bərabərdirsə, onda i-ci sorğu <(a[2i-1] + v) mod n, a[2i]> şəklində olur.
Giriş məlumatları
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əsinə bərabərdir. Üçüncü sətir 0-dan n - 1-ə qədər olan 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-u keçmir.
Çıxış məlumatları
Bütün sorğuların cavabları olan zirvələrin nömrələrinin cəmini çıxış faylına yazın.