Binary Tree Construction with Prime Leaves Optimization

You are given two integers n and m. Your task is to construct a binary tree according to the following rules:

• The root of the tree has weight n.
• Each node in the tree either has exactly two children or is a leaf (i.e. has 0 children).
• If a node has two children with weights a and b, then the node's weight n must equal the product: \(n = a\times b\).
• If a node is a leaf then its weight must be a prime number.
• You are also given m restrictions \(a_i\): no node in the tree is allowed to have a weight equal to any of the given \(a_i\>.

The goal is to construct such a tree in order to minimize the quantity:
\[ S = \sum_{i=1}^{k} \sum_{j=i}^{k} val_{\text{lca}(i,j)} \] where:

• k is the total number of nodes in the tree.
• vali is the weight of the i-th node (when nodes are numbered in the order you output them).
• lca(i, j) denotes the lowest common ancestor of nodes i and j in the tree.

If n is a prime number (and is not restricted), the only valid tree is a single node. If n is composite, you must factorize n as \(a\times b\) and recursively build trees for a and b (provided that the nodes do not use values from the forbidden set). Among all valid constructions, output any one that minimizes the sum S.

Note: It is guaranteed that for the given input there exists at least one valid tree construction.

inputFormat

The input consists of two lines:

1. The first line contains two integers n and m separated by a space.
2. The second line contains m distinct integers \(a_1, a_2, \ldots, a_m\) separated by spaces, representing the forbidden weights.

outputFormat

Output the constructed tree in the following format:

1. First, print an integer k — the total number of nodes in the tree.
2. Then, print k lines. For the i-th node (nodes are numbered in the order of a pre-order traversal starting from the root), print three integers: value L R where:
• value is the weight of the node.
• L is the index of its left child.
• R is the index of its right child.
3. If the node is a leaf, output -1 -1 for L and R.

sample

7 1
6

1
7 -1 -1