Rujia Liu Wario Land-ı sevir!
Mən "Wario Land" oyun seriyasını çox sevirəm, buna görə də onunla bağlı çox çətin (həqiqətən!!!) bir problem hazırlamaq istəyirəm :) Böyük təşəkkürlər Erjin Zhou-ya, ideya və referans kod üçün. Və kiçik təşəkkürlər Wenbin Tang-a, mənə xatırlatdığı üçün ki, Rujia Liu həmçinin L hərfini də ehtiva edir!
Tutaq ki, Wario Land-in başlanğıcında n yer var. Torpaq demək olar ki, köhnəlmişdir, buna görə də heç bir yol yoxdur! Sizə m əməliyyat veriləcək. Onları bir-bir icra edin və nəticələri çıxarın.
Giriş verilənləri
Giriş bir neçə test halını ehtiva edir. Hər bir test halında, birinci sətir üç tam ədəd n, m, k (1 ≤ n ≤ 50,000, 1 ≤ m ≤ 100,000, 2 ≤ k ≤ 33333) ehtiva edir. Yerlər 1-dən n-ə qədər nömrələnir. İkinci sətir n tam ədəd V[i] (1 ≤ V[i] ≤ k), hər yerin ilkin xəzinə dəyərlərini ehtiva edir. Növbəti m sətirin hər biri bir əməliyyatı ehtiva edir. Hər bir əməliyyat üçün, 1 ≤ x, y ≤ n, 1 ≤ v ≤ k. Giriş faylı son-of-file (EOF) ilə tamamlanır. Giriş faylının ölçüsü 10 MB-dan çox deyil.
Çıxış verilənləri
Hər bir tip-3 əməliyyat üçün, yerlərin sayını və onların xəzinə dəyərlərinin hasilini, k modulunda çıxarın. Əgər x və y arasında yol yoxdursa, və ya yol boyunca hər yerin xəzinə dəyəri > v isə, tək 0 çıxarın (nəinki 0 0 və ya 0 1).
Məxfiləşdirmə
Əməliyyatları əvvəlcədən emal etməyinizin qarşısını almaq üçün, aşağıdakı məxfiləşdirmə sxemini tətbiq edirik:
Hər bir tip-1 əməliyyat 1 x+d y+d olur Hər bir tip-2 əməliyyat 2 x+d v+d olur Hər bir tip-3 əməliyyat 3 x+d y+d v+d olur
Burada d bu əməliyyatı emal etməzdən əvvəl çıxardığınız son tam ədəddir. Əgər hələ heç nə çıxarmamısınızsa, d=0.
Məxfiləşdirmədən sonra, nümunə giriş belə olacaq:
4 8 39 2 3 4 5 1 1 2 3 2 3 5 1 1 3 3 2 3 5 1 25 28 3 27 28 28 3 11 12 13 3 4 5 2
Bu, proqramınızın oxuyacağı real girişdir.