Under construction

Still being built. Things may change

Sakura Reflection

Time limit1sMemory limit1024 MB

Summary
Given N axes at angles A_i, decide whether reflecting across each axis exactly once can return the image to its start, and output one valid order if so.
Level

Medium6 of 10

Topics
Geometry, Dynamic programming
Solved
No attempts yet

Problem

Album art of Ryu☆ - Sakura Reflection

Sakura Reflection is a song by Ryu☆, included on REFLEC BEAT. As the title says, now let us reflect the album art. You are given NN axes that pass through the center of the album art. The ii-th axis makes an angle of Ai∘A_i^{\circ} counterclockwise with the horizontal line. You can reflect the album art across each axis. Keep in mind that rotating the album art by an angle that is not a multiple of 360∘360^{\circ}, or reflecting it once across a single axis, does not return the album art to its original state.

Ryu☆ wants to reflect the album art NN times, using each of the NN axes exactly once. In the harsh world of reflections, the result can differ depending on the order of reflections. (a) reflects across the 60∘60^{\circ} axis and then the 120∘120^{\circ} axis. (b) reflects across the 120∘120^{\circ} axis and then the 60∘60^{\circ} axis.

Two reflection orders. The result can differ depending on the order.

Can the album art be returned to its original state by reflecting across each of the NN axes exactly once? If so, find one such order.

Input

The first line contains the number of axes NN. (1≤N≤500)(1 \le N \le 500)

The next line contains A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N, the angles the axes make with the horizontal line, separated by spaces. (0≤Ai≤179)(0 \le A_i \le 179)

All numbers in the input are integers.

Output

On the first line, print YES if the album art can be returned to its original state using the given axes, and NO otherwise.

If it is possible, print on the next line NN integers i1,i2,⋯ ,iNi_1, i_2, \cdots, i_N, separated by spaces, giving the axis numbers in the order they are used for reflection. Each iki_k must be a distinct integer from 11 to NN. After reflecting across the i1i_1-th, i2i_2-th, ..., iNi_N-th axes in that order, the album art must be in its original state.

Examples2

  1. Example 1

    Input
    4
    15 30 45 60
    
    Expected output
    YES
    4 3 1 2
    
  2. Example 2

    Input
    1
    90
    
    Expected output
    NO