AVL search tree update

Quido is developing a search engine which will manipulate millions of items in a relatively constrained memory space. To demonstrate the effectivity of his solution he is going to prepare a limited demo version which solves the task described bellow.

Denote by key(x) the value of the key of stored in a node x in an unempty AVL tree.
Define the left order of the node x as the number of nodes in the AVL tree which key value is smaller than key(x).
Operation Update(x, h) consists of two steps: In the first step, the node x is removed from the AVL tree by standard operation Delete. In the second step, if the AVL tree does not contain a node with key h than a new node with key h is inserted into the AVL tree by standard operation Insert.

To specify the task unambiguously, Quido follows the rules:

• A. Whenever it is necessary in the operation Delete to substitute the deleted node y by another node or to substitute the deleted key by another key in the AVL tree the implemenation will use the node (or the key of that node) which left order is equal to the left order of y increased by 1.
  
• B. Whenever the root of the AVL tree has only one child and the root is deleted, the child of the root becomes the new root of the AVL tree.
• C. Whenever an unbalanced node can be balanced by more types of rotations then a single rotation is always preferred over a double rotation.

The demo version generates a sequence of AVL trees (T₁, T₂, ..., T_K), K > 0, the sizes of these AVL trees are denoted (in this order) by the symbols N₁, N₂, ..., N_K.
The AVL tree T₁ is a balanced tree which depth is minimum possible and which contains all integer keys from the set {N, N+1, N+2, ..., N+2^D − 2}, where N and D are positive integers. Note that N₁ = 2^D − 1.

Let A, B, M be fixed positive integers. The AVL tree T_k+1 (k = 1, 2, ..., K−1) is obtained by modifying the AVL tree T_k with one operation Update:

• 1. In the AVL tree T_k is located the node x_k, which left order in T_k is equal to k² mod N_k.
  
• 2. The operation Update(x_k, (A×key(x_k) + B) mod M) is performed in T_k. The updated AVL tree is T_k+1.

     

Image 1. Example of an AVL tree before and after the operation Update(x, 4), the left order of x is 9. The left orders are written in a box at their respective nodes. The deleted and the inserted node are highlighted. Note the change of the left order of some other nodes.

The task

To check Quido's implementation we have to calculate the value of N_K, the depth of T_K and the number of those nodes in T_K which depth is equal to the depth of T_K.

---

Input

The input contains one text line with six positive integers K, N, D, A, B, M, separated by spaces. The meaning of the integers is described in the text above.
The value of K does not exceed 10⁶, the value of D does not exceed 23, all other input values do not exceed 10⁷.

Output

The otuput contains one text line with tree integers separated by spaces. The first integer is equal to N_K, the second one is equal to the depth of T_K and the third one is equal to the number of those nodes in T_K which depth is equal to the depth of T_K.
Let us remind you that the depth of the tree root is 0. You may suppose that the AVL tree's T₁, T₂, ..., T_K are unempty.

Example 1

Input

5 8 3 1 1 10

Output

6 2 3

The shape and the keys of the AVL tree T₅ are depicted bellow.

       _______[11]_____
  ____[3]____       [13]____
 [0]      [10]           [14]

Example 2

Input

10 2 4 2 3 5

Output

9 3 2

The shape and the keys of the AVL tree T₁₀ are depicted bellow.

      __________[11]_________
 ____[2]_____         ____[14]___
[0]      ___[4]      [12]      [15]___
        [3]                        [16]

Example 3

Input

100100 3 17 23233 2342 14301

Output

33752 16 79

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set