• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

فرض کنید گروه خونی هر انسان، یکی از ۸ حالت زیر را دارد:

$$O^- \quad O^+ \quad A^- \quad A^+ \quad B^- \quad B^+ \quad AB^- \quad AB^+$$

در واقع به عقیده‌ی زیست شناسان ۳ نوع ماده‌ی $A$، $B$ و $+$ وجود دارند که هر کدام از آن‌ها می‌توانند در خون ظاهر شوند یا نشوند. (نیامدن ماده‌ی $+$ را با $-$ نشان می‌دهند و نیامدن هیچ‌کدام از $A$ و $B$ را با $O$ نشان می‌دهند.)

می‌دانیم ماده‌های موجود در خون هر فرزند، زیرمجموعه‌ی اجتماع ماده‌های موجود در خون پدر و مادر او است. یعنی برای مثال اگر هیچ کدام از پدر و مادر در خون خود، ماده‌ی $A$ را نداشته باشند، امکان ندارد در خون فرزند ماده‌ی $A$ وجود داشته باشد. (برای فهم بهتر مثال‌های نمونه را مطالعه کنید.)

در یک آزمایشگاه $t$ آزمایش از خانواده‌های مختلف انجام شده و نتیجه‌ی آن گروه خونی پدر، مادر و فرزند را مشخص کرده است. از شما می‌خواهیم برنامه‌ای بنویسید که تشخیص دهد آیا هر کدام از این آزمایش‌ها درست انجام شده یا جواب آن‌ها با توجه به اطلاعات بالا، قابل قبول نیست.

در واقعیت گاهی گروه خونی فرزند نمی‌تواند همه زیرمجموعه‌های والدین باشد ولی ما برای سادگی سوال از آنها صرف‌نظر می‌کنیم.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت $t$ داده می‌شود که تعداد تست‌ها را نشان می‌دهد.

$$1 \leq t \leq 512$$

در $t$ سطر بعدی، در هر سطر سه رشته‌ی $d$، $m$ و $c$ که با یک فاصله از هم جدا‌شده‌اند داده می‌شود که به ترتیب گروه خونی پدر، مادر و فرزند را نشان می‌دهد.

گروه‌های خونی را با رشته‌های O-، O+، A-، A+، B-، B+، AB- و AB+ نمایش می‌دهیم.

خروجی

خروجی، $t$ سطر دارد و در هر سطر، در صورت قابل قبول بودن آزمایش، رشته‌ی valid و در غیر این‌صورت invalid را چاپ کنید.

مثال

ورودی نمونه ۱

3
AB+ A+ O-
B+ A- AB+
A+ A- B+

خروجی نمونه ۱

valid
valid
invalid

در آزمایش اول، گروه خونی پدر $AB^+$، گروه خونی مادر $A^+$ و گروه خونی فرزند $O^-$ است. کافی است هیچ‌کدام از ماده‌های $A$، $B$ و $+$ به فرزند منتقل نشود تا گروه خونی فرزند $O^-$ شود. پس نتیجه‌ی آزمایش قابل قبول است.

در آزمایش دوم، گروه خونی پدر $B^+$، گروه خونی مادر $A^-$ و گروه خونی فرزند $AB^+$ است. کافی است ماده‌های $B$ و $+$ از پدر و ماده‌ی $A$ از مادر به فرزند منتقل شود تا گروه خونی فرزند $AB^+$ شود. پس نتیجه‌ی آزمایش قابل قبول است.

در آزمایش سوم، گروه خونی پدر $A^+$، گروه خونی مادر $A^-$ و گروه خونی فرزند $B^+$ است. فرزند نمی‌تواند ماده‌ی $B$ در خون خود داشته باشد. (هیچ‌کدام از پدر و مادر این ماده را در خون خود ندارند.) پس نتیجه‌ی این آزمایش قابل قبول نیست.