Hello every one :D

How to solve this problem: Hashing: 2015-2016 ACM-ICPC, NEERC, Moscow Subregional Contest.

Thanks in advance.

How to calculate: a ^ n mod BASE with n is a big integer, a and n are not coprimes? I have a formula: a ^ n mod BASE = a ^ (n % phi(BASE) + phi(BASE)) mod BASE. Is this correct? Can somebody prove it if correct?

Thanks. (Sorry for my bad English).

I'm trying to solve a problem !

I have a tree. Plants with N nodes (N <= 100000).

For any node, the node level 1 is the direct child node and child node level K (K> 1) that all child nodes of the node level 1 level (K-1).

Initially, all nodes have the value 0

I have two queries:

1 u k e: all child note lever k of note u should be increased by e.

2 u: note u how much value.

input:

• The first line contains the number N

• N-1 line followed by the pair (u, v), v is the node level 1 of u

• The next line contains the number of queries M (M <= 500000).

• M line followed by queries.

output:

• results for each query 2.

Example

input:

6

1 2

1 3

2 4

3 5

3 6

6

2 6

1 1 2 1000

1 2 1 100

1 3 1 -100

2 4

2 5

output:

0

1100

900

Any ideal to solve it?

Thanks in advance.

(sorry if my English bad)