{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003eChef gives you a tree, consisting of \u003cb\u003eN\u003c/b\u003e nodes. The nodes are numbered from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e, and each node has an integer, which is equal to \u003cb\u003e0\u003c/b\u003e initially. Then, Chef asks you to perform \u003cb\u003eM\u003c/b\u003e queries.\r\n\u003cp\u003eThe first type of queries is \u003ci\u003echanging\u003c/i\u003e: here, you are given integers \u003cb\u003eX\u003c/b\u003e, \u003cb\u003eY\u003c/b\u003e, \u003cb\u003eA\u003c/b\u003e and \u003cb\u003eB\u003c/b\u003e. Add \u003cb\u003eA\u003c/b\u003e to the integer, associated with the node \u003cb\u003eX\u003c/b\u003e, then add \u003cb\u003eA+B\u003c/b\u003e to the integer, associated with the second node on the way from \u003cb\u003eX\u003c/b\u003e to \u003cb\u003eY\u003c/b\u003e, then add \u003cb\u003eA+2*B\u003c/b\u003e to the integer, associated with the third node on the way from \u003cb\u003eX\u003c/b\u003e to \u003cb\u003eY\u003c/b\u003e, and so on. As you know, there is only one simple path from \u003cb\u003eX\u003c/b\u003e to \u003cb\u003eY\u003c/b\u003e.\r\n\u003cp\u003eThe second type of queries is a \u003ci\u003equestion\u003c/i\u003e: here, you are given integers \u003cb\u003eX\u003c/b\u003e and \u003cb\u003eY\u003c/b\u003e. Output the sum of all integers, associated with nodes on the way from \u003cb\u003eX\u003c/b\u003e to \u003cb\u003eY\u003c/b\u003e.\r\n\u003cp\u003eThe third type of queries is a \u003ci\u003erollback\u003c/i\u003e: here, you are given an integer \u003cb\u003eX\u003c/b\u003e. All the integers associated with the nodes return to the state after the \u003cb\u003eX\u003c/b\u003e-th changing query. If \u003cb\u003eX\u003c/b\u003e is \u003cb\u003e0\u003c/b\u003e, then all of them become equal to zero, as in the very beginning.\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of an input consists of two integers - \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eM\u003c/b\u003e.\r\n\u003cp\u003eThen, \u003cb\u003eN−1\u003c/b\u003e lines follow. These \u003cb\u003eN−1\u003c/b\u003e lines describe the tree structure. Each line consists of two integers - \u003cb\u003eX\u003c/b\u003e and \u003cb\u003eY\u003c/b\u003e, and that means that there is an edge between node \u003cb\u003eX\u003c/b\u003e and node \u003cb\u003eY\u003c/b\u003e.\r\n\u003cp\u003eThen, \u003cb\u003eM\u003c/b\u003e lines follow. A single line denotes a single query, which has one of the following forms: (See the sample for the detailed explanation)\r\n\u003cul\u003e\r\n\u003cli\u003ec \u003cb\u003eX\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e \u003cb\u003eY\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e \u003cb\u003eA\u003c/b\u003e \u003cb\u003eB\u003c/b\u003e - \u003ci\u003echanging\u003c/i\u003e query,\u003c/li\u003e\r\n\u003cli\u003eq \u003cb\u003eX\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e \u003cb\u003eY\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e - \u003ci\u003equestion\u003c/i\u003e query,\u003c/li\u003e\r\n\u003cli\u003el \u003cb\u003eX\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e - \u003ci\u003erollback\u003c/i\u003e query. \u003c/li\u003e\u003c/ul\u003e\r\n\r\n\u003cp\u003eAs you can see, the numbers \u003cb\u003eX\u003c/b\u003e and \u003cb\u003eY\u003c/b\u003e aren\u0027t given to you directly. For the \u003ci\u003erollback\u003c/i\u003e query, actual number \u003cb\u003eX\u003c/b\u003e will be equal to \u003cb\u003e(X\u003csub\u003e1\u003c/sub\u003e+lastans) modulo (total number of \u003ci\u003echanging\u003c/i\u003e queries before this query + 1)\u003c/b\u003e. For the \u003ci\u003echanging\u003c/i\u003e and \u003ci\u003equestion\u003c/i\u003e queries, \u003cb\u003eX\u003c/b\u003e will be equal to \u003cb\u003e((X\u003csub\u003e1\u003c/sub\u003e+lastans) modulo N)+1\u003c/b\u003e and \u003cb\u003eY\u003c/b\u003e will be equal to \u003cb\u003e((Y\u003csub\u003e1\u003c/sub\u003e+lastans) modulo N)+1\u003c/b\u003e, where \u003cb\u003elastans\u003c/b\u003e denotes the last number that you have output, or zero if you haven\u0027t output any numbers yet.\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each \u003ci\u003equestion\u003c/i\u003e query output the answer on a single line.\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e1 ≤ \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eM\u003c/b\u003e ≤ 100000 (10\u003csup\u003e5\u003c/sup\u003e)\u003c/li\u003e\r\n\u003cli\u003e0 ≤ \u003cb\u003eA\u003c/b\u003e, \u003cb\u003eB\u003c/b\u003e ≤ 1000\u003c/li\u003e\r\n\u003cli\u003e0 ≤ \u003cb\u003eX\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eY\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e ≤ 100000 (10\u003csup\u003e5\u003c/sup\u003e)\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n\u003cb\u003eInput:\u003c/b\u003e\r\n5 7\r\n1 2\r\n2 3\r\n3 4\r\n4 5\r\nc 1 4 2 3\r\nc 2 3 5 10\r\nq 1 3\r\nl 1\r\nq 1 3\r\nl 1\r\nq 1 3\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n35\r\n0\r\n15\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003eAs you can see, the tree in the sample is like a line. Let\u0027s denote the first state of integers \u003cb\u003e0 0 0 0 0\u003c/b\u003e, where the \u003cb\u003ei\u003c/b\u003e-th integer means the integer associated with the node \u003cb\u003ei\u003c/b\u003e.\r\n\u003cp\u003eIn the first \u003ci\u003echanging\u003c/i\u003e query \u003cb\u003e\"c 1 4 2 3\"\u003c/b\u003e, the actual numbers are \u003cb\u003eX \u003d (1 + 0) modulo 5 + 1 \u003d 2, Y \u003d (4 + 0) modulo 5 + 1 \u003d 5\u003c/b\u003e. Hence the state will be \u003cb\u003e0 2 5 8 11\u003c/b\u003e after this query.\r\n\u003cp\u003eAfter the second \u003ci\u003echanging\u003c/i\u003e query \u003cb\u003e\"c 2 3 5 10\"\u003c/b\u003e, the state will be \u003cb\u003e0 2 10 23 11\u003c/b\u003e for similar reason.\r\n\u003cp\u003eIn the next \u003ci\u003equestion\u003c/i\u003e query, the actual numbers are \u003cb\u003eX \u003d (1 + 0) modulo 5 + 1 \u003d 2, Y \u003d (3 + 0) modulo 5 + 1 \u003d 4\u003c/b\u003e. Hence the answer must be \u003cb\u003e2 + 10 + 23 \u003d 35\u003c/b\u003e.\r\n\u003cp\u003eIn the first rollback query \u003cb\u003e\"l 1\"\u003c/b\u003e, the actual number is \u003cb\u003eX \u003d (1 + 35) modulo (2 + 1) \u003d 36 modulo 3 \u003d 0\u003c/b\u003e, since \u003cb\u003elastans \u003d 36\u003c/b\u003e. Thus the state will be rollbacked to \u003cb\u003e0 0 0 0 0\u003c/b\u003e.\r\n\u003cp\u003eThen the answer of the next \u003ci\u003equestion\u003c/i\u003e query \u003cb\u003e\"q 1 3\"\u003c/b\u003e must be 0, because all integers are currently 0.\r\n\u003cp\u003eIn the second rollback query \u003cb\u003e\"l 1\"\u003c/b\u003e, the actual number is \u003cb\u003eX \u003d (1 + 0) modulo (2 + 1) \u003d 1\u003c/b\u003e, since \u003cb\u003elastans \u003d 0\u003c/b\u003e. Thus the state will be \u003cb\u003e0 2 5 8 11\u003c/b\u003e, which is the state after the first \u003ci\u003echanging\u003c/i\u003e query.\r\n\u003cp\u003eThen the answer of the last \u003ci\u003equestion\u003c/i\u003e query must be \u003cb\u003e2 + 5 + 8 \u003d 15\u003c/b\u003e.\r\n"}}]}