+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نَقلی خیالی موجود است که مرحوم تورینگ فردی شکّاک و کم حافظه بود. او برای اینکه ماشین دلبندش دست نااهلان نیفتد رمزی عددی برای آن تعریف کرد. رمز عددی با ارقام کافی رمز مطمئنی بود چرا که ماشین دیگری نبود که بخواهد رمز را بشکند. از آنجا که وی نمی‌توانست رمز خود را حفظ کند تصمیم گرفت رمز خود را بر روی کاغذی یادداشت کند. از آنجا که کاغذ نیز ممکن بود دست نااهلان بیفتد او رمز را به صورت یک **رشته منطقی** روی کاغذ نوشت. از بد ماجرا گویا وی **دقیقا یک قسمت** از رشته منظقی را اشتباه یادداشت کرده‌بود و دیگر نمی‌توانست رمز خود را بازیابی کند. او همه بخش‌های رشته که به آن شک داشت را در وصیت‌نامه خود نوشت تا بلکه کسی رمز اصلی را بازیابد. رمزهای ممکن برای ماشین تورینگ را بازیابی کنید. توجه کنید شک‌های تورینگ از دو نوع زیر هستند: 1. او شک می‌کند که ادات $i$ـم رشته (از چپ) شاید $o$ بوده‌باشد. 2. او شک می‌کند که عدد $i$ـم رشته (از چپ) شاید $x$ بوده‌باشد. برای درک بهتر به مثال‌ها و توضیحات آنها توجه کنید. منظور از **رشته منطقی** یک رشته است که از [ادات‌های دودویی](https://fa.wikipedia.org/wiki/%D8%B9%D9%85%D9%84%DB%8C%D8%A7%D8%AA_%D8%A8%DB%8C%D8%AA%DB%8C) and, or و xor به ترتیب با نمادهای &, | و ^ به همراه **اعداد صحیح نامنفی** و **پرانتزگذاری کامل و معتبر** تشکیل شده‌است. منظور از **پرانتزگذاری کامل** این است که متناظر **هر ادات دقیقا یک پرانتز باز و یک پرانتز بسته** وجود دارد و این باعث عدم ابهام در اولویت عملگرها می‌شود. # ورودی در سطر اول ورودی $s$ یا همان رشته منطقی ابتدایی تورینگ می‌آید. همچنین در سطر بعد عدد $q$ تعداد شک‌های تورینگ می‌آید. سپس سطر $i$ـم از $q$ سطر بعد به یکی از دو شکل `1 k o` و `2 k x` است. که در شکل اول تورینگ شک می‌کند که شاید ادات $k$ـم رشته $o$ باشد که می‌دانیم $o$ یکی از & نماد and و | نماد or ویا ^ نماد xor است. در شکل دوم نیز تورینگ شک می کند که $k$ـمین عدد ظاهر شده در رشته شاید $x$ بوده باشد. توجه کنید که شک وی به ادات و عددی است که وجود دارد و به چیزی که وجود ندارد شک نمی‌کند ولی ممکن است رشته پس از شک او با رشته اولیه یکی باشد(مانند شک اول نمونه ۲). $$5 \le |s| \le 300 \, 000$$ $$1 \le q \le 300 \, 000$$ همچنین تضمین می‌شود تمام اعداد رشته ابتدایی و شک تورینگ **اعداد صحیح نامنفی و حداکثر میلیارد** باشند. # خروجی در سطر $i$ـم از $q$ سطر ارزش رشته منطقی حاصل از جایگذاری شک $i$ـم را خروجی دهید. توجه کنید شک‌ها تاثیری بر رشته ابتدایی نمی‌گذارند و از هم مستقل‌اند. # مثال ## ورودی نمونه ۱ ``` (5|1) 5 1 1 & 1 1 | 1 1 ^ 2 1 2 2 2 6 ``` ## خروجی نمونه ۱ ``` 1 5 4 3 7 ``` در شک اول، رشته برابر (1&5) است که مقدار آن برابر $1$ است. در شک دوم، رشته برابر $(5|1)$ است که مقدار آن برابر $5$ است. در شک سوم، رشته برابر (1^5) است که مقدار آن برابر $4$ است. در شک چهارم، رشته برابر $(2|1)$ است که مقدار آن برابر $3$ است. در شک پنجم، رشته برابر $(5|6)$ است که مقدار آن برابر $7$ است. ## ورودی نمونه ۲ ``` ((10&10)|(7^6)) 10 2 1 10 2 2 256 1 1 ^ 1 2 & 1 2 ^ 1 3 & 1 3 | 2 3 6 2 4 7 2 3 16 ``` ## خروجی نمونه ۲ ``` 11 1 1 0 11 14 15 10 10 30 ```

حل سؤال در بانک سؤالات