Rectangles on a Circle

Given several points on a circle, you are provided with the arc lengths between consecutive points in the circular order. All arc lengths are positive integers. Let \(T\) be the total circumference, i.e., \(T = \sum_{i=1}^{n} a_i\), where \(a_i\) are the arc lengths. A necessary condition for the existence of a rectangle inscribed in the circle is that \(T\) is even.

A rectangle inscribed in a circle must have its vertices as two pairs of diametrically opposite points. In other words, if we label the cumulative positions (angles) of the points as \(p_1, p_2, \ldots, p_n\) (with \(p_1=0\) and \(p_{i+1}=p_i+a_i\)), then for a point \(p_i\) there must exist another point whose position is \(p_i + \frac{T}{2}\) (modulo \(T\)). Each such pair forms a diameter. A rectangle is formed by two distinct diameters that do not share common points.

Your task is to identify whether there exist any four points that can form a rectangle and, if so, list all distinct rectangles. Two rectangles are considered the same if they have the same set of vertices.

Input Format:

• The first line contains an integer \(n\) (number of points).
• The second line contains \(n\) positive integers representing the arc lengths between consecutive points in circular order.

Output Format:

• The first line contains a single integer denoting the number of distinct rectangles formed.
• If there is at least one rectangle, then for each rectangle, output a line containing four space-separated integers. These integers represent the 1-indexed labels of the points that form the rectangle. For consistency, output the vertices in sorted order (in increasing order).

Constraints and Notes:

• \(1 \leq n \leq 10^5\)
• All arc lengths are positive integers.
• Use an efficient algorithm (ideally O(n)) in order to pass within tight time limits.
• If no rectangle can be formed, simply output 0.

Mathematical Note: The condition for two points \(p_i\) and \(p_j\) to be diametrically opposite is given by \(p_j \equiv p_i + \frac{T}{2} \pmod{T}\).

inputFormat

The input is given from the standard input in the following format:

 n
 a1 a2 a3 ... an

where \(n\) is the number of points and each \(a_i\) is a positive integer representing the arc length from the \(i\)-th point to the \((i+1)\)-th point (with the \(n\)-th point adjacent to the 1st point).

outputFormat

Output to the standard output:

• The first line is an integer representing the number of distinct rectangles.
• If at least one rectangle exists, for each rectangle output one line containing four space-separated 1-indexed integers denoting the vertices that form the rectangle, sorted in increasing order.

sample

4
3 3 3 3

1
1 2 3 4

</p>