The age of the Terminators has ended but not all is destroyed.

Treasure Hunter Gagan has discovered a secret vault built by the Machines that contains large amounts of pizza. The vault technology is beyond what any scientist has seen till date.

The vault is protected by a huge digital barrier that will only allow a Machine to pass through. The vault consists of an input port and an output port. The Machine that wishes to open the vault connects to both the ports. The vault provides some data through the output port and runs some challenges for the robot to complete. The robot accepts the data and provides the results for each challenge to the vault through the input port. Once the vault security system validation procedure is successfully completed, the door opens.

Gagan's partner Akash "DarkMatter" the hacker has provided Gagan information about the internal workings of the vault system.

On the inside, the vault consists of many layers of firewalls and filters. An initial set of data is provided to the robot by the system and the robot has to manipulate the data so that it can pass through every firewall and filter. The firewall accepts the result of averaging a particular segment of data while the filter manipulates the data in a particular segment in some way. (In this vault, the filter simply superimposes the word 'pizza' onto a data segment)

Each of the firewall layers checks whether the input given to it is proper and if so, the data passes through to the next level. However, if any firewall layer rejects an input, the door emits a microwave blast, frying the hapless intruder.

Gagan has weighed the benefits with the risks and has decided that the pizza behind the door is worth the risk of getting toasted. So he has placed an order to you for a machine that can emulate a robot authorized to open the door.

You are provided the initial set of data, consisting of N numbers. You are also provided information of Q layers consisting of 3 parts, the operation type, the left index and the right index.

Layers are of two types:

• Firewall: This layer requires you to print the average of the terms between the left and right indexes (both inclusive) from the current state of the data set.

• Filter: This layer requires you to add the word 'pizza' onto the terms between the left and right indexes (again both inclusive) of the data set. This is done as follows:

Each letter in the word 'pizza' corresponds to its position in the English alphabet (a=1, b=2 and so on). The corresponding number for each letter is added to each number that lies in the interval formed by the two indexes (both inclusive) in sequence. (See example below)

If the interval is smaller than 5, then as many letters as the interval size is added to the numbers. Say, if the interval is of size 3, the word 'piz' is added.

If the interval is larger than 5, the letters of the word 'pizza' repeat over the interval as many times as required. Say, if the interval size is 8, the word 'pizzapiz' is added.

Your work is to output the correct value of the output expected by each Firewall layer.

Input Format

The first line contains two numbers, N, the number of elements in the data set, and Q, the number of layers present.

The second line contains N numbers, giving the initial values of the set of data.

Q lines follow, which are each of the form X L R. X gives the operation type (0 for Filter and 1 for Firewall), L gives the left index and R gives the right index.

Output Format

For each Firewall operation, print the correct result of average in the form Numerator/Denominator in a new line. (No spaces in the output)

Constraints

1 <= N <= 2 x 10⁴

1 <= Elements in the initial data set <= 50

1 <= Q <= 2 x 10⁴

Notes

All layers are sequential. That is, the layers will appear in the same order as they are given in the input.