Submit | All submissions | Best solutions | Back to list |

## SOLVEIT - SOLVEIT |

Problem setter of INSOMNIA, MNNIT Allahabad decided to set a easy problem for all coders so that they can easily solve the problem and boost their confidence for rest of INSOMNIA.

The problem is a follows: You are given an array of size n which is initialized with 0. You will be given q queries of two types:

Type 1: set in (input value) index k to -1.

Type 2: print the index which has value -1 and is greater or equal to input index y. If there is no such value print -1.

Note: Indexing is 1 based.

### Input

First line contains two integers n and q separated by spaces.

Next q lines contains type of query and for type 1 query integer k separated by a space and for type 2 integer y separated by a space.

1 <= n <= 10^6

1 <= q <= 10^6

1 <= y, k <= n

### Output

Print a single line for each query type 2 containing index which has value -1 and is greater or equal to input index y.

### Example

Input:5 5 2 3 1 2 2 1 2 3 2 2Output:-1 2 -1 2

Added by: | Sandeep Kumar Singh |

Date: | 2017-08-04 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PYTHON PYPY PYTHON3 |