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

---

فرض کنید یک درخت دودویی با ارتفاع \(h\) و تعداد \(2h\) گره برگ داریم. هر گره درخت نیز دارای یک مقدار می‌باشد. تعریف می‌کنیم:

• اگر گره \(x\) برگ باشد، \(\alpha (x)\) برابر است با مجموعه شامل گره \(x\) و اجدادش تا ریشه درخت.(به همراه ریشه درخت)
• اگر \(x\) و \(y\) دو گره مجزا باشند، \(\alpha (x,y)\) برابر است با اجتماع \(\alpha (x)\) و \(\alpha (y)\)
• تابع \(f(x,y)\) حاصل جمع عناصر \(\alpha (x,y)\) را می‌دهد.

الگوریتمی ارائه دهید که برای یک درخت دودویی کامل دو گره برگ \(x^\*\) و \(y^\*\) را که مقدار \(f(x^\*, y^\*)\) برای آن‌ها حداکثر است را پیدا کند و \(f(x^\*, y^\*)\) را به عنوان خروجی برگرداند.

ورودی

یک عدد \(m\) که تعداد نمونه‌های مسئله را بیان می‌کند. سپس \(2m\) رشته که با زیر رشته pre: و یا post: شروع می‌شوند و هرکدام نشان‌دهنده‌ی دنباله‌ی prefix و یا postfix نمونه خود می‌باشند.

\[ 1 \le m \le 6\]

خروجی

برای هر نمونه ورودی یک عدد که نشان‌دهنده‌ی \(f(x^*,y^*)\) می‌باشد.

مثال

ورودی نمونه

1
pre: 36, 21, 15, 10, 19, 30, 20, 14, 6, 11, 5, 9, 10, 2, 7
post: 10, 19, 15, 20, 14, 30, 21, 5, 9, 11, 2, 7, 10, 6, 36

خروجی نمونه

141