Prefix Sum Query

You are given an array of n positive integers. Your task is to process q queries where each query can be of two types:

  1. Check if there is a prefix subarray of the given array with a sum equal to a given value s.

  2. Update the value at a specific index of the array.

Write a program to answer the queries efficiently.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 100 000), separated by a space, representing the size of the array and the number of queries, respectively.

The second line contains n positive integers, representing the elements of the array, where each element is positive and does not exceed .

The following q lines represent the queries. Each query is represented by a query type (1 or 2) followed by the necessary parameters:

  • For query type 1: an integer s.

  • For query type 2: an integer position p and a value x to update at that index.

Output

For each query of type 1, print YES if there exists a prefix subarray with a sum equal to s, otherwise print NO.

Examples

Input

Output

5 3
1 2 3 4 5
1 10
2 2 3
1 15

YES
NO

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue