Under construction

Still being built. Things may change

Consecutive Sums

Interview

Time limit1sMemory limit64 MB

Summary
Print every run of two or more consecutive positive integers that sums to N, ordered by starting value.
Level

Medium4 of 10

Topics
Math, Number theory
Solved
No attempts yet

Problem

Find every way to write a positive integer NN as a sum of two or more consecutive positive integers.

For example, N=9N = 9 has two such sums: 9=2+3+49 = 2 + 3 + 4 and 9=4+59 = 4 + 5.

Input

The first line contains the positive integer NN (3≤N≤10103 \le N \le 10^{10}).

Output

For each run of consecutive positive integers whose sum is NN, print the first addend and the last addend on one line, separated by a space.

Print the runs in increasing order of the first addend. Every NN given in the input has at least one such run.

Hint

The sum of kk terms starting at aa equals ka+k(k−1)2ka + \frac{k(k-1)}{2}.

Examples2

  1. Example 1

    Input
    10
    
    Expected output
    1 4
    
  2. Example 2

    Input
    27
    
    Expected output
    2 7
    8 10
    13 14