{"code":"xorpath","name":"Tổng xor của đường đi","description":"Cho trước một cây chỉ gồm một đỉnh $1$ (và cũng chính là *gốc* của cây). Nhiệm vụ của bạn là viết chương trình hỗ trợ thực hiện $Q$ truy vấn ở hai dạng sau:\r\n\r\n- `Add x y` - Thêm một đỉnh vào cây và cho nó làm một đỉnh con của đỉnh $x$. Đỉnh mới này và đỉnh $x$ được kết nối bởi một cạnh có trọng số là $y$. Số hiệu của đỉnh mới bằng số lượng đỉnh của cây trước khi thêm cộng cho $1$.\r\n- `Query a b` - Tìm đường đi dài nhất bắt đầu từ đỉnh $a$ và kết thúc tại một đỉnh thuộc cây con gốc $b$ (bao gồm chính đỉnh $b$). Độ dài của một đường đi được định nghĩa là tổng xor các trọng số của các cạnh nằm trên đường đi đó.\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa số nguyên dương $Q$ $(1\\leq Q\\leq 200,000)$ được nhắc đến ở đề bài.\r\n\r\n- Dòng thứ $i$ trong $Q$ dòng tiếp theo chứa thông tin về truy vấn thứ $i$ ở định dạng đã được mô tả ở đề bài. Các giá trị $x$, $a$ và $b$ thể hiện những đỉnh đang tồn tại ở trong cây tại thời điểm truy vấn và giá trị $y$ không vượt quá $2^{30}$.\r\n\r\n

Output

\r\n\r\n- Với mỗi truy vấn dạng `Query`, in ra một số nguyên trên một dòng riêng biệt thể hiện câu trả lời cho truy vấn tương ứng.\r\n\r\n

Scoring

\r\n\r\n- $25\\%$ số test có $Q\\leq 200$.\r\n- $25\\%$ số test khác có $Q\\leq 2000$.\r\n- $25\\%$ số test khác thỏa $b=1$ với mọi truy vấn `Query`.\r\n- $25\\%$ số test còn lại không có ràng buộc gì thêm. \r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 4\r\n Add 1 5\r\n Query 1 1\r\n Add 1 7\r\n Query 1 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 5\r\n 7\r\n ```\r\n \r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 6\r\n Add 1 5\r\n Add 2 7\r\n Add 1 4\r\n Add 4 3\r\n Query 1 1\r\n Query 2 4\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 7\r\n 2\r\n ```\r\n\r\n!!! question \"Test 3\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 10\r\n Add 1 4\r\n Add 1 9\r\n Add 1 10\r\n Add 2 2\r\n Add 3 3\r\n Add 4 4\r\n Query 4 2\r\n Query 1 3\r\n Add 6 7\r\n Query 1 3\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 14\r\n 10\r\n 13\r\n ```","points":450.0,"partial":true,"time_limit":3.5,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}