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

فرض کنید یک درخت دودویی با ارتفاع $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