Q548: Tree

你的任務是找出一棵二元樹中最小路徑上終端節點(樹葉,leaf node)的值。所謂路徑乃指從根節點(root)旅行到任一終端節點。路徑的值為所經過的節點的值的和(包含根節點及終端節點)。而最小路徑就是指路徑值最小的那條。

Input

每組測試資料2列,用來描述一棵二元樹。第一列的序列為以中序旅行(inorder traversal)所經過的節點的值。第二列的序列為以後序旅行(postorder traversal)所經過的節點的值。

各列中所有的值都是整數(大於0,小於10000),且值都不同。你可以假設二元樹的節點數最多10000,最少1。輸入列的長度最長不會超過1000000。

Output

對每組測試資料,請輸出二元樹中最小路徑上終端節點的值。如果有不止一條最小路徑,請輸出終端節點值最小的值。

Sample Input

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

Sample Output

1
3
255