123A.md (1607B)
1 Source: https://codeforces.com/problemset/problem/123/A 2 3 A. Prime Permutation 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 You are given a string *s*, consisting of small Latin letters. Let's denote the length of the string as |*s*|. The characters in the string are numbered starting from 1. 22 23 Your task is to find out if it is possible to rearrange characters in string *s* so that for any prime number *p* ≤ |*s*| and for any integer *i* ranging from 1 to |*s*| / *p* (inclusive) the following condition was fulfilled *s**p* = *s**p* × *i*. If the answer is positive, find one way to rearrange the characters. 24 25 Input 26 27 The only line contains the initial string *s*, consisting of small Latin letters (1 ≤ |*s*| ≤ 1000). 28 29 Output 30 31 If it is possible to rearrange the characters in the string so that the above-mentioned conditions were fulfilled, then print in the first line "YES" (without the quotes) and print on the second line one of the possible resulting strings. If such permutation is impossible to perform, then print the single string "NO". 32 33 Examples 34 35 Input 36 37 ``` 38 abc 39 ``` 40 41 Output 42 43 ``` 44 YES 45 abc 46 ``` 47 48 Input 49 50 ``` 51 abcd 52 ``` 53 54 Output 55 56 ``` 57 NO 58 ``` 59 60 Input 61 62 ``` 63 xxxyxxx 64 ``` 65 66 Output 67 68 ``` 69 YES 70 xxxxxxy 71 ``` 72 73 Note 74 75 In the first sample any of the six possible strings will do: "abc", "acb", "bac", "bca", "cab" or "cba". 76 77 In the second sample no letter permutation will satisfy the condition at *p* = 2 (*s*2 = *s*4). 78 79 In the third test any string where character "y" doesn't occupy positions 2, 3, 4, 6 will be valid.