This problem can be solved in several ways; one approach is as follows:

Graph Construction

Construct a new graph ( nodes n+1 to 2n ) where all edge weights are multiplied by k.
Connect the two graphs such that:

• For each edge u → v with weight w, add an edge u → v+n with weight w × k
  or
• For every node u, add an edge u → u+n with weight 0

Algorithm

Run the Bellman–Ford algorithm
→ either modify to find max instead of min,
→ or make edge weights negative and then use the standard Bellman–Ford algorithm.

This will help find the maximum score from node 1 to either n or 2n
(since using the operation at most once also includes not using it).

Case for -1

Case for -1 will be when we detect a positive cycle,
but will it be always wrong??

Observation

No, in case the positive cycle does not lie in the path from 1 to n/2n,
we will not print -1 —
i.e., there exists a positive cycle but if we go in that path,
we cannot reach n/2n.

(Example: test case 103)

This is a constructive problem.

Let’s analyze all possible combinations of consecutive bits and how their OR and AND behave.

Key Observations

1. Invalid Combination:
   For (OR, AND) = (0, 1) there is no valid configuration.
   Hence, if this case appears in the input, the answer is immediately -1.

2. Fixed Configurations:

• (OR, AND) = (0, 0) → Only possible as (0, 0)
• (OR, AND) = (1, 1) → Only possible as (1, 1)
  So these positions are fixed during construction.

1. Flexible Configurations:
   For (OR, AND) = (1, 0), there are two valid possibilities:

• (0, 1) or (1, 0)
  These will be the free bits to be filled later between fixed ones.

1. Continuity Constraint:
   You cannot have consecutive fixed pairs like:

• (00) followed by (11) directly, or
• (11) followed by (00)
  because they contradict continuity in construction.

1. Parity Observation:
   Between any two fixed configurations:

• (00 → 00) or (11 → 11) ⇒ only even number of (OR, AND) = (1,0) configurations allowed
• (00 → 11) or (11 → 00) ⇒ only odd number of (OR, AND) = (1,0) configurations allowed

If this parity condition is not met, the answer is -1.

Construction Approach

1. Check invalid pairs:
   If any (OR, AND) = (0, 1) → print -1.

2. Fix known bits:
   Mark all positions where (OR, AND) is (0,0) or (1,1).

3. Check for conflicts:
   If any contradiction appears between fixed bits → print -1.

4. Fill middle parts:

• Between two fixed blocks, fill alternately using the parity rule.
• If no fixed blocks exist at all, fill arbitrarily as:
  • 010101... or
  • 101010...

1. Verification:
   After construction, verify that the generated array indeed satisfies all (OR, AND) pairs.
   If yes, add the corresponding bit to the final answer.

Mutliple answer can be possible.