human
Alice's hair is growing by leaps and bounds. Maybe the cause of it is the excess of vitamins, or maybe it is some black magic...

To prevent this, Alice decided to go to the hairdresser. She wants for her hair length to be at most l centimeters after haircut, where l is her favorite number. Suppose, that the Alice's head is a straight line on which n hairlines grow. Let's number them from 1 to n. With one swing of the scissors the hairdresser can shorten all hairlines on any segment to the length l, given that all hairlines on that segment had length strictly greater than l. The hairdresser wants to complete his job as fast as possible, so he will make the least possible number of swings of scissors, since each swing of scissors takes one second.

Alice hasn't decided yet when she would go to the hairdresser, so she asked you to calculate how much time the haircut would take depending on the time she would go to the hairdresser. In particular, you need to process queries of two types:

  * 0 — Alice asks how much time the haircut would take if she would go to the hairdresser now. 
  * 1 p d — p-th hairline grows by d centimeters. 


Note, that in the request 0 Alice is interested in hypothetical scenario of taking a haircut now, so no hairlines change their length.

Input

The first line contains three integers n, m and l (1 ≤ n, m ≤ 100 000, 1 ≤ l ≤ 10^9) — the number of hairlines, the number of requests and the favorite number of Alice.

The second line contains n integers a_i (1 ≤ a_i ≤ 10^9) — the initial lengths of all hairlines of Alice.

Each of the following m lines contains a request in the format described in the statement.

The request description starts with an integer t_i. If t_i = 0, then you need to find the time the haircut would take. Otherwise, t_i = 1 and in this moment one hairline grows. The rest of the line than contains two more integers: p_i and d_i (1 ≤ p_i ≤ n, 1 ≤ d_i ≤ 10^9) — the number of the hairline and the length it grows by.

Output

For each query of type 0 print the time...
Solve the task in PYTHON.
assistant
#Here is Python program to find the time the haircut would take.

#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    from math import gcd
    # from pickle import dumps
    # from queue import PriorityQueue, Queue

if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    def gcd(x, y):
        """gcd(x, y) -> int
        greatest common divisor of x and y
        """
        while y:
            x, y = y, x % y
        return x

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new...