The twentieth century begins

The 20th century has begun, bringing with it a new breed of more dangerous criminals involved in politics and international affairs. One day, one such criminal steals a crucial document that could potentially spark a major war. The renowned detectives, Sherlock Holmes and Dr. Watson, are called in to solve the case.

Upon arriving at the crime scene, Holmes and Watson discover that the stolen document was kept in a locked safe. The criminal managed to open the safe using a special device but, in their haste, left the device behind. Holmes examines the device and finds that it has ( n ) slots for numbers and two key functions:

• Increase the p-th element by d. Notably, the device retains the previous state, meaning no information is lost when this operation is performed.

• Calculate the sum of numbers within the range ([l, r]).

Since the device keeps a record of all previous states, these functions allow access to any past state of the device.

Holmes realizes that if he can decipher the algorithm behind the device, he might be able to trace its creator. Your task is to develop this algorithm.

Input

The first line contains two integers, n ((1 $\le$ n $\le$ 100,000)) and m ((1 $\le$ m $\le$ 100,000)), where n is the number of slots in the device, and m is the number of queries.

The next m lines contain queries of two types:

• 1 x p d - From state x, create a new state by increasing the p-th element by d.

• 2 x l r - In state x, calculate the sum of numbers in the range ([l, r]).

Initially, all slots in the device are set to zero. This initial state is numbered 0. All slot positions in the device start from one. There will be no queries for non-existent states. When processing a query of the second type, a new state is created and assigned the number j + 1, where j is the number of the last added state, with j initially being 0.

Output

For each query of the second type, output the result on a separate line.

Examples