{"raw_statement":[{"iden":"statement","content":"De Prezer loves functions. He has invented a new function f named Troynacci .\n\nf(1) and f(2) are given to you. If i > 2, f(i) = af(i - 2) + bf(i - 1) .\n\nDe Prezer also has got a sequence x1, x2, ..., xn .\n\nDe Prezer also loves query. So he gives you q queries. In each query, he gives you numbers l and r (l ≤ r) and for each i that l ≤ i ≤ r, you should increase xi by f(i - l + 1) .\n\nAt last, you should print the final sequence. Of course, members of sequence could be very large, so you should print them modulo 109 + 7 .\n\nThe first line of input contains two integers n and q.\n\nThe second line contains two integers f(1) and f(2) .\n\nThe third line of input contains two integers a and b .\n\nThe forth line of input contains n space separated integers x1, x2, ..., xn .\n\nThe next q lines, each line contains two integers l and r .\n\n1 ≤ n, q ≤ 105\n\n1 ≤ f(1), f(2), a, b ≤ 109\n\n0 ≤ xi ≤ 109 (for each 1 ≤ i ≤ n)\n\nPrint the final sequence in a single line.\n\n"},{"iden":"input","content":"The first line of input contains two integers n and q.The second line contains two integers f(1) and f(2) .The third line of input contains two integers a and b .The forth line of input contains n space separated integers x1, x2, ..., xn .The next q lines, each line contains two integers l and r .1 ≤ n, q ≤ 1051 ≤ f(1), f(2), a, b ≤ 1090 ≤ xi ≤ 109 (for each 1 ≤ i ≤ n)"},{"iden":"output","content":"Print the final sequence in a single line."},{"iden":"examples","content":"Input6 61 11 10 0 0 0 0 01 61 14 52 24 45 6Output2 2 2 5 7 9"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\{[, ]\\}^* $ be a valid parentheses string representing a rooted forest, where each matching pair $[ \\ ]$ corresponds to a node, and nested pairs represent ancestor-descendant relationships.\n\n**Constraints**  \n1. $ 1 \\leq |s| \\leq 1000 $  \n2. $ s $ is a well-formed sequence of balanced brackets.\n\n**Objective**  \nCompute the number of connected components in the forest, which equals the number of top-level (non-nested) bracket pairs in $ s $.  \n\nThat is, count the number of times a matching pair $[ \\ ]$ occurs at depth 0.  \n\nEquivalently:  \nLet $ d = 0 $.  \nInitialize $ \\text{components} = 0 $.  \nFor each character $ c $ in $ s $:  \n- If $ c = '[' $: increment $ d $. If $ d = 1 $, increment $ \\text{components} $.  \n- If $ c = ']' $: decrement $ d $.  \n\nOutput $ \\text{components} $.","simple_statement":"Count the number of connected components in a forest represented by a string of balanced parentheses. Each pair of parentheses represents a node, and nested parentheses represent parent-child relationships. Output the count as an integer.","has_page_source":false}