Limits 1s, 512 MB

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

-How?

-Read the statement carefully!

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 + 34 + 43 + 33 + 34*3 = 79.

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 Pth 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

Input

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 <= 105
1 <= O,H <= 106
1 <= P <= Number of days till now - 1
1 <= V <= 106

Output

For each query of type 3 print "Day #x: y" where x is number of the day and y is required answer modulo 109 + 7.

Sample

InputOutput
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

Submit

Login to submit.

Statistics

67% Solution Ratio
mahdi.hasnatEarliest, Dec '19
Kuddus.6068Fastest, 0.1s
nusuBotLightest, 130 MB
Mah1r_Shortest, 2005B
Toph uses cookies. By continuing you agree to our Cookie Policy.