Tree Coloring

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Chef has recently learnt about binary trees and immediately fell in love with them. His best friend Shasha has promised him to gift a binary tree only if he is able to show his love for binary trees by solving the following problem about binary trees.
Given a complete binary tree T consisting of N nodes labelled from 1 to N. The node with label 1 is the root of the tree. For a node labelled v, its' left child will be labelled as 2*v (provided it exists) and right child as 2*v+1 (provided it exists).
Initially, all the nodes of tree are uncolored.
Chef has to perform Q queries on tree T where each query can have one of the following three types:
 1 X K
Update the tree T such that node X becomes uncolored, all the nodes at distance 1 from X get colored with color 1, all nodes at distance 2 from X get colored with color 2, and so on up to nodes at distance K from X.
Formally, color all nodes that are at distance (1 ≤ D ≤ K) units from node X with color D and make node X colourless.
Please note that when we say node at distance D from node X, you have to consider all the nodes in the tree, not just the ones in the subtree of X.
 2 X Y
Count the number of distinct colors on the unique simple path from node X to node Y.
 3 X
Count the number of distinct colors in the subtree rooted at node X.
Input
The first line of input contains two space separated integer numbers N and Q denoting the number of nodes in the tree T and number of queries to be processed respectively.
Each of the following Q lines contains a query of one of the above mentioned three types.
Output
For each query of type 2 and 3, print the sought answer.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 50000
 1 ≤ X, Y ≤ N
 0 ≤ K ≤ 10^{5}
Subtasks
 Subtask 1 (32 pts) : 1 ≤ N, Q ≤ 1000
 Subtask 2 (68 pts) : original constraints
Example
Input 10 10 2 3 5 3 1 1 2 2 2 3 5 1 3 2 2 3 5 3 1 1 7 5 3 1 2 3 5 output 0 0 2 2 2 5 4
Author:  ma5termind 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/COLORING 
Tags  datastructure, ltime35, ma5termind, queries, segment, tree 
Date Added:  29032016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 