{"raw_statement":[{"iden":"statement","content":"You are given a node of the tree with index 1 and with weight 0. Let _cnt_ be the number of nodes in the tree at any instant (initially, _cnt_ is set to 1). Support _Q_ queries of following two types:\n\n*   Add a new node (index _cnt_ + 1) with weight _W_ and add edge between node _R_ and this node.\n*   Output the maximum length of sequence of nodes which\n    1.  starts with _R_.\n    2.  Every node in the sequence is an ancestor of its predecessor.\n    3.  Sum of weight of nodes in sequence does not exceed _X_.\n    4.  For some nodes _i_, _j_ that are consecutive in the sequence if _i_ is an ancestor of _j_ then _w_\\[_i_\\] ≥ _w_\\[_j_\\] and there should not exist a node _k_ on simple path from _i_ to _j_ such that _w_\\[_k_\\] ≥ _w_\\[_j_\\]\n\nThe tree is rooted at node 1 at any instant.\n\n**Note that the queries are given in a modified way.**"},{"iden":"input","content":"First line containing the number of queries _Q_ (1 ≤ _Q_ ≤ 400000).\n\nLet _last_ be the answer for previous query of type 2 (initially _last_ equals 0).\n\nEach of the next _Q_ lines contains a query of following form:\n\n*   1 p q (1 ≤ _p_, _q_ ≤ 1018): This is query of first type where and . It is guaranteed that 1 ≤ _R_ ≤ _cnt_ and 0 ≤ _W_ ≤ 109.\n*   2 p q (1 ≤ _p_, _q_ ≤ 1018): This is query of second type where and . It is guaranteed that 1 ≤ _R_ ≤ _cnt_ and 0 ≤ _X_ ≤ 1015.\n\ndenotes bitwise XOR of _a_ and _b_.\n\nIt is guaranteed that at least one query of type 2 exists."},{"iden":"output","content":"Output the answer to each query of second type in separate line."},{"iden":"examples","content":"Input\n\n6\n1 1 1\n2 2 0\n2 2 1\n1 3 0\n2 2 0\n2 2 2\n\nOutput\n\n0\n1\n1\n2\n\nInput\n\n6\n1 1 0\n2 2 0\n2 0 3\n1 0 2\n2 1 3\n2 1 6\n\nOutput\n\n2\n2\n3\n2\n\nInput\n\n7\n1 1 2\n1 2 3\n2 3 3\n1 0 0\n1 5 1\n2 5 0\n2 4 0\n\nOutput\n\n1\n1\n2\n\nInput\n\n7\n1 1 3\n1 2 3\n2 3 4\n1 2 0\n1 5 3\n2 5 5\n2 7 22\n\nOutput\n\n1\n2\n3"},{"iden":"note","content":"In the first example,\n\n_last_ = 0\n\n\\- Query 1: 1 1 1, Node 2 with weight 1 is added to node 1.\n\n\\- Query 2: 2 2 0, No sequence of nodes starting at 2 has weight less than or equal to 0. _last_ = 0\n\n\\- Query 3: 2 2 1, Answer is 1 as sequence will be {2}. _last_ = 1\n\n\\- Query 4: 1 2 1, Node 3 with weight 1 is added to node 2.\n\n\\- Query 5: 2 3 1, Answer is 1 as sequence will be {3}. Node 2 cannot be added as sum of weights cannot be greater than 1. _last_ = 1\n\n\\- Query 6: 2 3 3, Answer is 2 as sequence will be {3, 2}. _last_ = 2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}