ლოლიპოპი

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

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

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

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

წყარო: პოლონეთი, ოლიმპიადა 18, ეტაპი 1


ბაიტასარს აქვს ტკბილეულის მაღაზია ბაიტბურგში. ბაიტბურგში მყოფ ბავშვებს შორის ყველაზე პოპულარული ტკბილეული არის ვანილისა და მარწყვის ლოლიპოპი (ჩუპაჩუპსი). ეს ლოლიპოპები შედგებიან სხვადასხვა ტიპის სეგმენტებისგან, რომლებსაც ერთნაირი სიგრძე აქვთ. თითოეულს მხოლოდ ერთი გემო აქვს: ვანილის ან მარწყვის. ლოლიპოპის ფასი დამოკიდებულია სეგმენტების ფასის ჯამზე. ვანილის სეგმენტი ღირს 1 ბაიტალარი ხოლო მარწყვის სეგმენტი 2 ბაიტალარი.

 

 

█████░░░░░████░░░░░████

ნახ.1

 

ნახ. 1: მოყვანილი 5 სეგმენტიაი ლოლიპოპი, რომელიც შედგება 3 მარწყვისა და 2 ვანილის სეგმენტისგან ერთმანეთის მონაცვლეობითაა მილაგებული, ჯამური ფასი არის 8 ბაიტალარი.

 ამ ეტაპისთვის, ბაიტმენს აქვს მხოლოდ ერთი (სავარაუდოდ ძალიან გრძელი) ლოლიპოპი მარაგში. გამყიდველი აცნობიერებს, რომ შესაძლოა არავის უნდოდეს მისი მთლიანად ყიდვა, რის გამოც იძლევა შესაძლებლობას რომ (ვანილის ან მარწყვის) კიდეში გადატეხოს ლოლიპოპი, რომ უფრო პატარა ზომის გაყიდოს.  საბოლოო ფრაგმენტი, რომელიც გაიყიდება უნდა იყოს გაუტეხავი, ანუ მთლიანი.

 გამოცდილებამ აჩვენა რომ მომხმარებლები ხშირად ყიდულობენ ლოლიპოპს იმ ფასად, თუ რამდენი ფულიც უდევთ ჯიბეში (სულ რამდენიც უდევთ მთლიანად ხარჯავენ, ანუ შევაჭრბა არ გამოვა). ბაიტასარი ფიქრობს იმ k ვარიანტზე, თუ როგორ დატეხოს თავისი ლოლიპოპი, რომ მიიღოს ზუსტად k ბაიტალარი. რადგან დავალება მარტივი არ არის, ამიტომ დახმარებას გთხოვთ თქვენ.

 

შეყვანა

ტანდარტული შესაყვანი ინფორმაცია შეიცავს ორ მთელ რიცხვს n და m-ს 1<=n,m<=1,000,000. ისინი გამოყოფილები არიან 1 სფეისით. ლოლიპოპის სეგმენტები გადანომრილია 1 დან n-მდე (ანუ n სეგმენტიანი ლოლიპოპი გვაქვს), ხოლო შესაძლო მნიშვნელობები არის k.  input-ის შემდეგი ხაზი შეიცავს n-ცალ სიმბოლოს T და W, რომლებიც შესაბამისად ასახავენ T=მარწყვი W=ვანილი. i-ური სეგმენტს შეესაბამება i-ური სიმბოლო(მარწყვი ან ვანილი). Ხოლო input-ის შემდეგი m ხაზი შეიცავს k-ს მნიშვნელობებს, სადაც 1 <= k <= 2,000,000. თითო ხაზზე თითო მნიშვნელობაა მოცემული.

 

 

შედეგი

თქვენმა პროგრამამ უნდა OUTPUT-ში უნდა გამოიტანოს ზუსტად m ცალი ხაზი. თუ  მოცემული k-ს მნიშვნელობით ვერ ტყდება ლოლიპოპი ისე, რომ ფასი იყოს ზუსტად k ბაიტალარი, მაშინ უნდა გამოიტანოთ nie.  თუარადა გამოიტანოთ l და r სფეისით გამოყოფილი, სადაც 1 <= l <= r <= n, რაც ნიშნავს რომ ლოლიპოპის ფრანგმენტი l დან r მდე ღირს ზუსტად k ბაიტალარი. თუ k-სთვის რამდენიმე პასუხი მოიძებნება, დააბრუნეთ ერთ-ერთი.




მაგალითები

შესატანი მონაცემები
5 3 TWTWT 5 1 7 დაკოპირება
გამოსატანი მონაცემები
1 3 2 2 NIE დაკოპირება

შენიშვნა

მაგალითის ახსნა: ეს მაგალითი აღწერს ლოლიპოპს ნახატი ნომერი 1-დან.
Input-ში გადანომრილია 1 დან 3მდე, რომ შეადგინოს TWT ლოლიპოპი, რომელიც 5 ბაიტალარი ღირს, ანუ სწორია.

 სეგმენტი N2 არის ვანილის და ღირს 1 ბაიტალარი ანუ ესეც გამოდის.

 ხოლო ამ ლოლიპოპით ვერანაირად ვერ მიიღებ ისეთ ლოლიპოპს, რომელიც ღირს 7 ბაიტალარი, შესაბამისად გამოვიტანთ NIE-ს.

 

თარგმანი შესრულებულია გივი ბერიძის მიერ