eolymp
bolt
Try our new interface for solving problems
Problems

Irish Whiskey

Irish Whiskey

Time limit 1 second
Memory limit 128 MiB

You are given an array A of n integers (1-indexed). Your task is to perform queries of two types:

  1. Swap A[l] and A[r].

  2. Find if subarray A[l, ... r] is sorted in non-decreasing order.

Input data

The first line contains two integers n and q (1n300 000, 1q200 000), the length of the array and the number of queries.

The second line contains n integers: the elements of the array (1A[i]10^9) separated by spaces.

The following q lines contain descriptions of the queries. Each line begins with integer type which equals 1 or 2 and specifies the type of query. It is followed by integers l and r separated by a space (1lrn).

Output data

For each query of the second type, output a single line with "Ja" or "Nein" (without quotes).

Examples

Input example #1
3 3
1 2 3
2 1 3
1 2 3
2 1 3
Output example #1
Ja
Nein
Source 2014 Петрозаводск, Moscow IPT Contest, Август 23, Задача I