Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

-Onions make us cry, don’t they? They can make us happy too.

-How?

-Read the statement carefully!

Scientist **Dr. Shiku** has created genetically modified Onions in his laboratory. Each day he tries to create new types of onions and preserves them. Onions created in each day are preserved in a new jar. This jar has two values **(O,H)** associated with it. This pair of values **(O,H)** is called the **‘O-Pair’** of this jar.**O = Number of onions in it.****H = Happiness value.**

You can increase or decrease the number of onions **O** by the happiness value **H**. That means **(O,H)** can be transformed into **(O’,H’) = (O + H , H ) or ( O - H , H ) when H<=O**.

You can increase or decrease the Happiness value **H** by the number of Onions **O**. That means **(O,H)** can be transformed into **(O’,H’) = (O, H + O ) or ( O , H - O ) when O<=H**.

If there are Jars that can reach the same **‘O-pair’** by performing the above operation any number of times they are considered **‘Same Group’**. Now make an array of happiness values from a ‘Same Group’. **‘Ultimate Happiness value’** for each group is defined as the sum of the product of each subset of the array.

For example (1,3),(1,4),(1,3) are the O-Pairs of the same group. Now let’s make an array by taking the happiness values of the jars of this same group. The array is [ 3 , 4 , 3 ]. So, the ultimate happiness value of this group is 3 + 4 + 3 + 3*4 + 4*3 + 3*3 + 3*4*3 = 79.

You are the assistant of the great scientist **Dr. Shiku**. He asked you to write a program that will help him to take the research far. Each day **Dr. Shiku** needs the program to perform three kinds of queries:

**Type 1:** pair of integers **(O,H)** will be given. The program has to store information about the new jar that is created today.**Type 2:** An integer **P** will be given. The lab will now contain only the jars which were there on the P^{th} day.

To understand the Type 2 query: Let Dr Shiku had jars of O-pairs (1,3), (1,4) on the second day and he created a new jar of O-pair (1,6) on the third day. So, on the third day, he has jars of (1,3), (1,4) and (1,6). If Dr. Shiku asks you to perform a query of type 2 where P = 2 on the fourth day then Dr. Shiku will only have the jars of the second day. That means on the fourth day Dr. Shiku has the jars of O-pairs (1,3) and (1,4) that were on the second day.

**Type 3**: An integer **V** will be given. You have to smile and print the sum of the **‘Ultimate Happiness Value’** of the groups formed by the Onion jars in the lab that can reach **(O’,H’)<=(V,V)**.**(O,H) is less than or equal to (V,V) when O’<=V and H’<=V.**

Counting large values for query type 3 is the ultimate happiness for you. Please smile! :D

First line of the input will contain an integer D. Number of days.
On each day you will be given any one of the queries:**1 O H**

or,
**2 P**

or,
**3 V**

First integer of each query represents the query type described in the description.

**1 <= D <= 10 ^{5}**

For each query of type 3 print **“Day #x: y”** where x is number of the day and y is required answer modulo **10 ^{9} + 7**.

Input | Output |
---|---|

10 1 2 2 1 1 3 1 1 4 1 1 3 3 1 3 2 3 5 2 3 3 1 3 2 | Day #5: 79 Day #6: 81 Day #7: 81 Day #9: 19 Day #10: 21 |

33% Solution Ratio

mahdi.hasnatEarliest,

mahdi.hasnatFastest, 0.1s

mahdi.hasnatLightest, 132 MB

mahdi.hasnatShortest, 3166B

Login to submit