E. Love Marriage
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Shanto has finally decided that it's time for him to get married!

Although it took a while for him to reach this decision, it didn't take long for the news to spread like wildfire. Soon, Shanto's phone started to ring nonstop, with $$$n$$$ girls requesting to chat with him, each seeing him as a perfect life partner. Being overwhelmed, Shanto devised an algorithm to find his favorite girl.

Here's his plan:

  • Tomorrow, Shanto will chat with the girls one by one in the order they called.
  • For every girl, Shanto will calculate the happiness he feels during the chat.
  • At any point, Shanto will keep track of the favorite girl he's met so far.
  • After chatting with the first girl, she's automatically the favorite girl (for now).
  • For subsequent girls:
    • If the happiness Shanto feels chatting with her is less than that of the current favorite girl, he will stick with his favorite girl.
    • If it's greater, she will become the new favorite girl.
    • If it's equal, Shanto will flip an unbiased coin. If the coin lands on heads, he will stick to his current favorite girl. Otherwise, this girl will become the new favorite girl.
  • If Shanto can finish chatting with all the girls, he will choose his favorite girl to become his wife.
  • However, at any point, if Shanto chats with $$$k$$$ consecutive girls and no girl strictly surpasses his maximum happiness, he'll cancel the rest of the dates and go to sleep. In this case, his current favorite girl gets to become "Mrs. Shanto"!

Being an honest boy, Shanto shares all the details about the algorithm with the girls. But here's a twist: Shanto himself doesn't know the value of $$$k$$$ yet. Influenced by one of his roommates, Shanto has developed a habit of making important decisions at the last moment. So, he decided to sleep on it and choose $$$k$$$ tomorrow morning.

Meanwhile, the girls, excited and anxious, started fantasizing about their chances. Some have tried to read Shanto's mind and guess the value of $$$k$$$. Others have decided to pray for an optimal $$$k$$$ to maximize their chances. Now, they've turned to you, the only person who can predict Shanto's happiness levels, for help.

Your task is to calm their nerves by answering their queries.

Input

The first line of the input contains two space-separated integers $$$n\:(2 \le n \le 10^5)$$$ and $$$q\:(1 \le q \le 2 \times 10^5)$$$ — the number of girls who called Shanto and the number of queries.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — where $$$a_i\:(1 \le a_i \le 10^9)$$$ is the predicted happiness Shanto will feel when chatting with the $$$i$$$-th girl.

Then $$$q$$$ lines follow, each containing a query of one of the following two types:

  • "1 i k": the $$$i$$$-th girl $$$(1 \le i \le n)$$$ asks about the probability of her becoming Shanto's wife for the given value of $$$k\:(1 \le k \le n)$$$.
  • "2 i": the $$$i$$$-th girl $$$(1 \le i \le n)$$$ asks about the optimal value of $$$k$$$ that maximizes the probability of her becoming Shanto's wife and the corresponding probability.
Output

For each query, output the corresponding answer in a line.

For each query of type 1, output one integer $$$p\:(0 \le p \lt 10^9 + 7)$$$.

For each query of type 2, output two space-separated integers $$$k\:(1 \le k \le n)$$$ and $$$p\:(0 \le p \lt 10^9 + 7)$$$. If multiple values of $$$k$$$ are optimal, you can output any of them.

Output all probabilities modulo $$$(10^9 + 7)$$$. Formally, if a probability can be expressed as an irreducible fraction $$$\displaystyle\frac{x}{y}$$$, you have to output $$$p = xy^{-1}\: mod \:(10^9 + 7)$$$, where $$$y^{-1}$$$ is an integer such that $$$yy^{-1}\: mod\: (10^9 + 7) = 1$$$.

Example
Input
15 6
5 2 7 6 3 7 2 4 4 7 5 9 1 10 9
1 1 1
1 3 5
2 6
2 9
2 14
2 12
Output
1
500000004
5 500000004
1 0
15 1
8 0
Note

In the sample test case, if $$$k = 5$$$, Shanto will chat with the first $$$8$$$ girls and then go to sleep. Here, the $$$3$$$rd girl and the $$$6$$$th girl are valid candidates for being Shanto's favorite girl, each having a $$$\displaystyle\frac{1}{2}$$$ probability of becoming Shanto's wife.