Mysterious Inscription
Mr. Sherlock Holmes is feeling quite bored. For several months, he hasn't come across a single intriguing case, so he spends his time playing chess with Watson. However, Holmes soon receives a letter from Inspector Gregson about the mysterious death of an American, whose body was discovered in an abandoned house on Brixton Road. The most puzzling detail was a sequence of numbers written on the wall of the victim's room.
Sherlock Holmes, with his keen detective skills, deduced that this sequence is an encrypted key. Dr. Watson proposed squaring each number in the sequence and then calculating the sum of elements over a specified part of the sequence. Holmes found this idea appealing. To preserve the previous results, they decided to write down the newly formed sequence on a new sheet after each squaring. Given that the sequence can be quite large, they seek your assistance.
The operations of squaring and summing should be performed modulo 2014.
Input
The first line contains two integers n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 100000), where n is the number of elements in the sequence, and m is the number of queries.
The second line contains n natural numbers, which make up the sequence.
The following m lines contain queries of two types:
1 x l r - for the sequence numbered x, calculate the sum over the interval [l, r];
2 x - generate a new sequence from sequence x, where each element is squared.
All query numbers and sequence positions start from one. It is guaranteed that there will be no queries for non-existent versions. When processing a query of the second type, a new version is created, which is assigned the number j+1, where j is the number of the last added sequence, with the initial value j = 0.
Output
For each sum query, output the result on a separate line.