Video Doubling Period

In order to better measure video quality, Kuaishou's product manager has proposed the concept of the video doubling period. For a video, let its current accumulated play count be \(x\). Define \(T = \lceil x/2 \rceil\). Let the video reach a cumulative play count \(T\) for the first time at time \(j'\) (with \(j' \ge 0\), where time 0 represents the initial state before any requests are processed) and suppose a query arrives at time \(j\). Then the doubling period is defined as \(j - j'\).

There are \(n\) videos numbered from 1 to \(n\). Xiao Zhang, a back‐end administrator at Kuaishou, has \(m\) seconds of work during a week. Every second, a request arrives from the front end. The requests are of two types:

• Update request: In one second, all videos numbered in the interval \([l, r]\) gain \(x\) additional plays.
• Query request: The front end asks for the doubling period for video \(i\) at the current time. (Assume the current cumulative play count of video \(i\) is \(x\); then the required doubling period is \(j - j'\), where \(j'\) is the time when the video first reached a cumulative count greater than or equal to \(\lceil x/2 \rceil\); note that initially, at time 0, each video’s play count is 0.)

Your task is to process the \(m\) requests sequentially and output the doubling period for each query request.

Note: In an update request, when a video’s play count increases from \(a\) to \(a+x\), it is assumed that all intermediate counts \(a+1, a+2, \ldots, a+x\) are "achieved" at the update time if they have not been achieved before. For example, if a video has an initial count of 0 and receives an update of 5 plays at time 1, then counts 1, 2, 3, 4, 5 are all considered to have been reached at time 1.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of videos and the number of seconds (i.e. requests) respectively.

Each of the next \(m\) lines represents a request. A request is in one of the two formats:

• 1 l r x — an update request: for every video with index in \([l, r]\), add \(x\) plays.
• 2 i — a query request: output the doubling period for video \(i\) at the current time.

Time is counted in seconds starting from 1. Initially (at time 0), every video has 0 plays, and this is considered to have been achieved at time 0.

outputFormat

For each query request, output one integer on a separate line: the doubling period for the queried video.

sample

3 5
1 1 2 5
2 1
1 2 3 2
2 2
2 3

1
3
2