CF633G Yash And Trees

Yash loves playing with trees and gets especially excited when they have something to do with prime numbers. On his 20th birthday he was granted with a rooted tree of $ n $ nodes to answer queries on. Hearing of prime numbers on trees, Yash gets too intoxicated with excitement and asks you to help out and answer queries on trees for him. Tree is rooted at node $ 1 $ . Each node $ i $ has some value $ a_{i} $ associated with it. Also, integer $ m $ is given. There are queries of two types: 1. for given node $ v $ and integer value $ x $ , increase all $ a_{i} $ in the subtree of node $ v $ by value $ x $ 2. for given node $ v $ , find the number of prime numbers $ p $ less than $ m $ , for which there exists a node $ u $ in the subtree of $ v $ and a non-negative integer value $ k $ , such that $ a_{u}=p+m·k $ .

The first of the input contains two integers $ n $ and $ m $ ( $ 1

For each of the queries of the second type print the number of suitable prime numbers.