To better measure video quality, Kuaishou product managers have proposed the concept of a video's "doubling period." The doubling period is a time-based metric measured in seconds, defined as the time it takes for a video's cumulative view count to grow from half of its current total to its current total. Low-quality videos often start strong but fade quickly; users click out of curiosity or due to clickbait titles, but after some time, their reputation drops sharply, resulting in a long doubling period. High-quality videos often start slow but gain momentum; after people watch them, they spontaneously share and recommend them, gradually accumulating reputation and traffic, resulting in a shorter doubling period.

Xiao Zhang is a video backend administrator at Kuaishou, responsible for monitoring $n$ videos, numbered from $1$ to $n$. Xiao Zhang has $m$ seconds of working time in a week. Every second, a request arrives from the frontend, which can be one of two types:

• Update request: During this second, all videos with IDs in the range $[l, r]$ receive $x$ views, and the backend data needs to be updated.
• Query request: The frontend wants to know the doubling period of the video with ID $i$. Let the current cumulative view count of the video for this week be $x$, and let the query request arrive at second $j$. If the video's cumulative view count for this week first reached $\lceil x / 2 \rceil$ at second $j'$ ($j' \ge 0$), then the doubling period is defined as $j - j'$.

Faced with such high-frequency update and query demands, Xiao Zhang finds it a bit tricky and hopes for your help.

Input

The first line contains two positive integers $n$ and $m$, where $1 \le n, m \le 10^5$.

The next $m$ lines, where the $j$-th line represents the request at second $j$ ($1 \le j \le m$), are in one of the following two formats:

• $0 \ l \ r \ x$: This is an update request. At second $j$, videos with IDs in the range $[l, r]$ ($1 \le l \le r \le n$) receive $x$ views. It is guaranteed that $1 \le x \le 10^8$.
• $1 \ i$: This is a query request. Query the doubling period of the video with ID $i$ ($1 \le i \le n$) at second $j$.

Output

For each query request, output one line representing the queried doubling period.

Examples

Input 1

5 5
0 2 3 3
1 4
0 2 4 3
1 4
1 3

Output 1

2
1
4

Note 1

• At second $2$, the cumulative view count of video $4$ is $0$. It reached a cumulative view count of $\lceil 0 / 2 \rceil = 0$ at second $0$, so the doubling period for video $4$ at this time is $2$ seconds.
• At second $4$, the cumulative view count of video $4$ is $3$. It reached a cumulative view count of $\lceil 3 / 2 \rceil = 2$ at second $3$, so the doubling period for video $4$ at this time is $1$ second.
• At second $5$, the cumulative view count of video $3$ is $6$. It reached a cumulative view count of $\lceil 6 / 2 \rceil = 3$ at second $1$, so the doubling period for video $3$ at this time is $4$ seconds.