एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

Zuma गेम बनाना

आपने Zuma नाम का एक गेम बनाने का फैसला किया है। इस गेम में आप उन हिस्सों (सेगमेंट) को हटाने की प्रक्रिया पर काम कर रहे हैं, जिनमें एक ही रंग की बॉल्स एक-दूसरे से टकरा जाती हैं। मान लीजिए एक बॉल्स की पंक्ति है, जिसमें अलग-अलग रंग हैं, और खिलाड़ी किसी एक रंग की बॉल को उस पंक्ति में किसी ख़ास स्थान पर शूट करता है। यदि उसमें शामिल बॉल सहित कुल 3 या उससे ज़्यादा बॉल एक ही रंग की हो जाती हैं, तो वह पूरा सेगमेंट हट जाता है, और आस-पास की बॉल्स मिलकर उस खाली जगह को भर देती हैं।
notion image
अगर 3 या अधिक बॉल्स टकराने पर एक ही रंग की होती हैं, तो वह सेगमेंट भी गायब हो जाता है। यह सिलसिला तब तक चलता रहता है जब तक कि टकराने वाले हिस्सों के रंग अलग-अलग न हों या पंक्ति में बॉल्स ही न बचें।

इनपुट

इनपुट की पहली पंक्ति में एक स्ट्रिंग b (1 ≤ |b| ≤ ) होती है, जो पंक्ति में मौजूद बॉल्स के रंगों का प्रतिनिधित्व करती है। बॉल्स के रंग लोअरकेस लैटिन अक्षरों के रूप में दिए जाते हैं (उदाहरण के लिए, y पीले के लिए, b नीले के लिए, r लाल के लिए, आदि)।
अगली पंक्ति में वह इंडेक्स i दिया होता है जिस पर खिलाड़ी बॉल shoot करता है (1 ≤ i ≤ |b|), और बॉल का रंग c (लोअरकेस लैटिन अक्षर) होता है।

आउटपुट

कार्यक्रम को अंतिम रूप से बची हुई बॉल्स की पंक्ति को प्रिंट करना चाहिए।

Examples

Input
Output
rrryyrrb 4 y
b
rgbbrg 3 b
rgrg
ggrrrbbb 1 g
rrrbbb
gbyw 1 y
ygbyw
cabbbacc 4 b
caacc

Explanation

  1. rrryyrrb → rrryyyrrb → rrrrrb → b
  1. rgbbrg → rgbbrg → rgrg
  1. ggrrrbbb → gggrrrbbb → rrrbbb
  1. gbyw → ygbyw
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue