კოლაიდერი

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: GEOI, 2010, დასკვნითი, XI-XII კლასი


ფიზიკოსები ატარებენ ექსპერიმენტს სამი ტიპის (x, y და z) ნაწილაკთა თვისებების გამოსაკვლევად. ისინი კოლაიდერში უშვებენ ამ ნაწილაკთა გადანომრილ მწკრივს, რომელიც შედგება ზუსტად n (1 ≤ n ≤ 1,000,000) ცალი ნაწილაკისაგან. ექსპერიმენტის დროს ხდება ზემოქმედება კონკრეტულ ნაწილაკზე, რის შედეგადაც ის ქრება მწკრივის i-ური ადგილიდან და მყისიერად ჩნდება სხვა j-ურ ადგილას (1 ≤ i, j ≤ n). ნაწილაკის გაქრობის შემდეგ მის მარჯვნივ მდგომი ნაწილაკების ნომრები 1-ით მცირდება, ხოლო მწკრივში გაჩენის შემდეგ მის მარჯვნივ აღმოჩენილ ნაწილაკთა ნომრები 1-ით იზრდება. ზემოქმედებათა გარკვეული რაოდენობის შემდეგ ფიზიკოსებს აინტერესებთ რომელი ნაწილაკი დგას ამჟამად k-ურ (1 ≤ k ≤ n) ადგილას. დაწერეთ პროგრამა, რომელიც დაეხმარება ფიზიკოსებს ამ პრობლემის გადაჭრაში.   
 
    შესატანი მონაცემები:
    ფაილის პირველ სტრიქონში არის ორი ნატურალური რიცხვი: n – ნაწილაკების რაოდენობა და m – ზემოქმედებათა და შეკითხვათა ჯამური რაოდენობა. მეორე სტრიქონში მოცემულია x, y და z სიმბოლოებისაგან შედგენილი n სიგრძის მქონე მიმდევრობა. მომდევნო m (1 ≤ m ≤ 15,000) სტრიქონიდან თითოეულში აღიწერება ზემოქმედება ან შეკითხვა: სტრიქონი, რომელშიც აღწერილია ზემოქმედება, იწყება “a” სიმბოლოთი და ჰარის შემდეგ მასში მოცემულია ორი ნატურალური რიცხვი [1; n] ინტერვალიდან, რომელთაგან პირველი აღნიშნავს ნაწილაკის საწყის მდგომარეობას, ხოლო მეორე – საბოლოო მდგომარეობას. სტრიქონი, რომელშიც აღწერილია შეკითხვა, იწყება “q” სიმბოლოთი და ჰარის შემდეგ მასში მოცემულია ერთი ნატურალური რიცხვი [1; n] ინტერვალიდან, რომელიც აღნიშნავს იმ პოზიციას, რომელზეც მყოფი ნაწილაკი აინტერესებთ ფიზიკოსებს. 
 
    გამოსატანი მონაცემები
    ფაილში გამოიტანეთ იმდენი სტრიქონი, რამდენი შეკითხვაცაა შემომავალ ფაილში. i-ურ სტრიქონში უნდა იყოს i-ური შეკითხვის პასუხი – შესაბამისი ნაწილაკის (x, y ან z) დასახელება.
 
 



მაგალითები

შესატანი მონაცემები
15 6 xzxyyzxxzxyyzyx a 2 10 a 15 4 q 3 a 12 2 q 14 q 2 დაკოპირება
გამოსატანი მონაცემები
y z y დაკოპირება