Algorithms and Data Structures

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.
  1. 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: 1.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

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