Module: الشجرة الديكارتية

Problem

يتم منحك مصفوفة & nbsp؛ a & nbsp؛ of size & nbsp؛ n & nbsp؛ & nbsp؛ q & nbsp؛ من الاستعلامات إليها. هناك نوعان من الطلبات:

• 1 & nbsp؛ l _i & nbsp؛ r _i & nbsp؛ & mdash؛ إجراء تحول دوري للمقطع & nbsp؛ [ l _i ، & thinsp؛ r _i ] & nbsp؛ إلى اليمين . أي ، لكل & nbsp؛ x مثل & nbsp؛ l _i & thinsp؛ & le؛ & thinsp؛ x & thinsp؛ & lt ؛ & thinsp؛ r _i ، & nbsp؛ a _{x & thinsp؛ + & thinsp؛ 1 & nbsp؛ تصبح مساوية للقيمة السابقة & nbsp؛ a x و & nbsp؛ a li & nbsp؛ تصبح مساوية لـ القيمة السابقة & nbsp؛ a ri ؛}
• 2 & nbsp؛ l _i & nbsp؛ r _i & nbsp؛ & mdash؛ اقلب المقطع [ l _i ، & thinsp؛ r _i ].

نبسب ؛
من الضروري إخراج المصفوفة بعد معالجة جميع الطلبات.
نبسب ؛
إدخال
يحتوي السطر الأول على عددين صحيحين & nbsp؛ n و & nbsp؛ q & nbsp؛ (1 & thinsp؛ & le؛ & thinsp؛ n ، & thinsp؛ q < / em> & thinsp؛ & le؛ & thinsp؛ 2 & middot؛ 10 ⁵ ).
يحتوي السطر الثاني على & nbsp؛ n 2 ، ...، & nbsp؛ a _n & nbsp؛ (1 & thinsp؛ & le؛ & thinsp؛ a _i & thinsp؛ & le؛ & thinsp؛ 10 ⁹ ).
تعال بعد ذلك & nbsp؛ q & nbsp؛ line. & nbsp؛ i منهم يحتوي على ثلاثة أعداد صحيحة & nbsp؛ t _i ، & nbsp؛ l _i ، & nbsp؛ r _i ، حيث & nbsp؛ t _i & nbsp؛ & mdash؛ اكتب & nbsp؛ i الاستعلام الخامس ، & nbsp؛ [ l _i ، & thinsp؛ r _i ] نبسب ؛ & [مدش] ؛ المقطع الذي يتم تنفيذ الاستعلام عليه (1 & thinsp؛ & le؛ & thinsp؛ t _i & thinsp؛ & le؛ & thinsp؛ 2، & nbsp؛ 1 & thinsp؛ & le؛ & thinsp؛ l _i & thinsp؛ & le؛ & thinsp؛ r _i & thinsp؛ & le؛ & thinsp؛ n ). <ر /> نبسب ؛
بصمة
طباعة & nbsp؛ m & nbsp؛ number، & nbsp؛ i th منها يساوي الرقم الموجود في الموضع & nbsp؛ b _i & nbsp؛ بعد معالجة جميع الطلبات.

<الجسم>

أدخل	الإخراج
6 3 1 2 3 4 5 6 2 1 3 2 3 6 1 1 6	1 3 2 6 5 4

(ج) كورباتوف إي ، 2018