Irish Whiskey

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

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

The second line contains n integers: the elements of the array (1 ≤ A[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 (1 ≤ l ≤ r ≤ n).

Output

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

Examples