Random Integer Generator Using a Binary Integer Generator

Problem

0과 1을 리턴하는 함수 get_random_binary()가 있습니다.

이 함수는 다음과 같이 이미 정의 되어 있습니다.
Python:

from random import randrange
def get_random_binary():
    return randrange(2)

get_random_binary <- function(){
  sample(0:1,1)
}

이 함수만을 이용하여 0과 주어진 n-1까지의 랜덤값을 리턴하는 함수get_rand_int(n)을 구현하세요.

예제

실행: get_rand_int(12)
결과: 0 or 1 or 2 or 3 or 4... or 11

제약사항 : Python, R 두가지 언어중 하나로 구현합니다.

R Markdown이나 Jupyter notebook으로 아이디어부터 구현에서 실험, 테스트, 결과까지 정리해서 제출해야 합니다. 시각화나 통계검증을 위한 라이브러리등의 패키지는 자유롭게 사용하셔도 됩니다.(ggplot, matplotlib, seabron, scipy…) 하지만 내장된 랜덤 함수는 사용하시면 안됩니다.

Solution

문제 풀이 접근 방법은 get_rand_int()를 이용해 이진수를 생성하고, 이진수를 십진수로 바꾸고, 생성되는 십진수가 원하는 숫자 n보다 클 경우 다시 이진수를 생성 한다.

절차는 다음과 같습니다:

Process

Step 1:
2^k > n 에서 가능한 가장 작은 k를 찾는다

Step 2:
k길이의 list를 생성한다

Step 3:
list를 get_random_binary() 함수를 통해 생성되는 0 또는 1로 채운다

Step 4:
생성된 이진 난수를 십진수로 바꾼다

Step 5:
십진수 output이 n 보다 클 경우, 위 Step 3와 Step 4를 반복한다

Code

get_random_binary 함수
문제에서 주어진 함수. uniform 분포에 따라 0 또는 1을 생성한다.

get_random_binary <- function(){
  sample(0:1,1)
}
get_random_binary()

[1] 1

bin2int 함수
이진수를 십진수로 바꾸는 함수다.

bin2int <- function(x){
  if(!is.numeric(x)){
    throw("Only numeric inputs are allowed")
  }
  
  x %>% 
  as.character() %>%   # 이진수를 string으로 변환 
  str_split("") %>%    # string의 각 요소를 분리 
  unlist() %>%         # list를 vector로 변환
  {rev(. == 1)} %>%    # 후 계산을 위해 순서를 바꾸고 boolean으로 변환
                       # {}로 전 단계의 output을 evaluation 한다
  which() %>%          # TRUE인 index를 찾는다. 이진수의 자릿수 이다
  {2^(.-1)} %>%        # 2**자릿수를 계산해 십진수로 변환
  sum()                # 합을 구한다
}
#bin2int("1001010101")
bin2int(100101101011111)

[1] 19295

get_rand_int 함수
문제에서 주어진 get_random_binary()를 이용한 난수 생성 함수다.

get_rand_int <- function(n){
  if(n == 0){
    throw("0 is outside the allowed subset")
  } else if (!is.numeric(n)){
    throw("Only numeric inputs are allowed")
  } else if (n == 1) {
    0
  } else {
    x <- n - 1                         # n-1 저장하기
    k <- 0                            # Step 1: 이진수의 길이 k 구하기
    while(x/2**k > 1){
     k = k + 1
    }
    
    list <- 1:k                       # Step 2: k길이의 list 생성 
    out_int <- n                      
    while(out_int > x){               # Step 3, 4, 5: while을 이용한 난수 생성
      out_int <-                      
        sapply(list, 
               function(y) y = get_random_binary()) %>% # Step 3: list를 0,1로 채움
        {as.numeric(paste(., collapse = ""))} %>%       # Step 3: 이진수 생성
        bin2int()                                       # Step 4: 이진수를 십진수라 바꾼다
    }
    out_int
  }
}
#get_rand_int(0)
#get_rand_int(1)
#get_rand_int("12")
get_rand_int(12)

[1] 6

Test

Exploratory Data Analysis

sample_fun 함수 get_rand_int() 함수를 이용해 sampling을 한다. nsim은 sampling 횟수이고, n은 get_rant_int(n)의 n이다.

sample_fun <- function(nsim, n){
  list <- numeric(nsim)
  out <- sapply(list, function(x) x = get_rand_int(n))
  out
}

n=12이라는 가정하에, get_rand_int() sampling을 100,000번 시도한다

df <- sample_fun(nsim = 100000, n = 12)
df <- data.frame(df)
head(df, 10)

각 숫자가 몇번 생성이 됬는지 알아보자.

table(df)

df
   0    1    2    3    4    5    6    7    8    9   10   11 
8347 8216 8293 8428 8420 8509 8226 8194 8368 8321 8415 8263

0 에서 11이 생성으로 인해 단순 평균은 5.5와 어느정도 비슷해야한다.

df %>% 
  plyr::summarize(mean = mean(df))

     mean
1 5.49901

생성된 자료의 평균 5.51 은 5.50와 비슷하다.

ggplot을 이용해 uniform distribution인 것 같은지 살펴본다.

ggplot(df, aes(x = df)) +
  geom_histogram(binwidth = 1) +
  theme_minimal() +
  ylab("반복 횟수") +
  theme_set(theme_gray(base_family="AppleGothic")) +
  theme(axis.title.x = element_blank()) +
  scale_x_discrete(limits = 0:11)

Figure 2. 난수 생성 10만번 반복 결과

보다시피 uniform distribution인것 처럼 보이지만 통계적 검증이 필요하다.

Statistical Testing

어떠한 사람이든 연산적인 방법으로 난수 생성을 고려 하는 자는 당연히 죄의 상태에 이르렀다… 난수 생성이라는 것은 없다. 그저 난수 생성하는 법만 있을 뿐이다. 우리는 단순히 숫자를 만드는 요리 레시피를 다룰 뿐이다.
- Monte Carlo Method (1951), John von Neumann

우리가 생성한 난수는 연산 방법으로 구한 의사 난수이기에 통계적으로 검증을 해야한다. 함수에서 생성된 자료가 난수인지를 확실하게 알려면 다음 두가지 조건이 충족되야한다:
1. 통계적으로 유의한 수준에서 uniform 분포를 따른는지
2. 숫자간에 상관관계가 있는지

생성된 자료는 정규 분포를 따르지 않으므로, 비모수적 통계적인 검증 방법을 세가지 시도해본다:
1. 자료의 예상 및 관측된 빈도로 chi-square goodness of fit test를 이용한 uniform distribution 검증.
2. 생성된 수간의 독립성을 검증하는 Wald-Wolfowitz runs test.
3. 생성된 수의 계열 상관 검증 (serial correlation test).

위 세가지 검정은 내부적인 난수 생성 함수를 쓰지 않으므로 제약 조건을 충족한다.

Chi-square Goodness of Fit Test

난수 생성이 uniform 분포를 따를시 예측 되는 빈도와 관측된 빈도를 비교해 chi-square test를 통해 두 표본이 다른지를 검증한다.

\[H_o: 생성된\;수의\;예상\;빈도와\;관측\;빈도가\;같다\] \[H_a: 생성된\;수의\;예상\;빈도와\;관측\;빈도가\;같지\;않다\]

df_chi <- cbind(observed = table(df),
                expected = 100000/12)
df_chi

   observed expected
0      8347 8333.333
1      8216 8333.333
2      8293 8333.333
3      8428 8333.333
4      8420 8333.333
5      8509 8333.333
6      8226 8333.333
7      8194 8333.333
8      8368 8333.333
9      8321 8333.333
10     8415 8333.333
11     8263 8333.333

chisq.test(df_chi)


    Pearson's Chi-squared test

data:  df_chi
X-squared = 6.4039, df = 11, p-value = 0.8451

p-value 0.9896은 유의 수준 0.05보다 현저히 크기 때문에 귀무가설을 채택하고 생성된 난수들의 예측 빈도와 관측 빈도가 같다고 판단을 내린다. 즉 chi-square test for independence를 통해 uniformity는 주장 할 수 있지만, 무작위성을 검증하기에는 통계적 검증력이 다른 방법에 비해 낮다고 알려져있고[1] 숫자간에 트렌드가 있는지를 판단 할 수 없다. 만약 트렌드가 있다면 무작위성을 주장 할 수 없다.

Wald-Wolfowitz Runs Test

다음은 Wald-Wolfowitz Runs Test를 살펴보자. chi-square test보다는 통계적 검정력이 높기로 알려져 있고[2], 트렌드를 검증할 수 있는 장점이 있다. 다음수가 전수보다 클 경우 +, 작을 경우 -로하고 모든 수를 계산한다. +와 -의 조합의 모든 경우의 수를 계산하고 조합 검정을 한다.

\[H_o: 생성된\;시퀀스는\;무작위로\;생성됐다\] \[H_a: 생성된\;시퀀스는\;무작위로\;생성되지\;않았다\]

runs.test(df$df)


    Runs Test

data:  df$df
statistic = -1.5024, runs = 45164, n1 = 49787, n2 = 41704, n = 91491, p-value = 0.133
alternative hypothesis: nonrandomness

p-value인 0.5882는 유의수준 0.05보다 높은 것으로 보아 귀무가설을 채택하고 생성된 자료의 무작위성을 받아들일 수 있다.

Serial Correlation Test

특정한 경우에는 von Neumann rank test가 runs test보다 뛰어나다고 알려져 있으므로[3] 마지막으로 rank test로 무작위성을 검증 해보자. 연속적으로 이어지는 숫자들의 상관 계수 \(\rho_1\)를 계산한다. \[H_o: \rho_1 = 0\] \[H_a: \rho_1 \neq 1\]

BartelsRankTest(df$df,alternative = "trend")


    Bartels Ratio Test

data:  df$df
RVN = 1.99390, z = -0.96386, n = 100000, p-value = 0.1676
alternative hypothesis: trend

p-value는 0.829로, 유의수준인 0.05보다 월등히 높다. 현재의 자료에서는 숫자와 전숫자의 lag인 k = 0일 경우와 lag k = 1일 경우의 분포는 의존도가 없는 것으로 판단 할수 있지만, lag k = 100 까지를 계산을 하자. 이를 하기 위해선 연산이 간편한 계열 상관계수를 계산해보자. 상관계수가 0에 가까우면 수가 무작위로 생성이 됬다고 판단을 내릴 수 있다.

df_shift <- shift(df, n = 1:100, fill = get_rand_int(12), type = "lag")
df_shift <- do.call("cbind", df_shift)
df_shift.cor <- cor(df_shift)
corrplot(df_shift.cor,
         tl.pos = "n")

Figure 3. Lag k = 100까지의 상관계수들의 correlation 표.

Figure 4. lag = 10000 까지의 auto-correlation

같은 표본간의 상관계수는 당연히 1 (파랑색) 이지만, 표본간의 상관계수는 모두 0인것으로 보여, k = 10000까지는 표본관의 의존도가 없는것으로 보고, 생성된 자료의 무작위성을 입증 할 수 있다.

Conclusion

get_random_binary()를 통해 만든 get_rand_int() 함수를 만들었고, get_rand_int()에서 나오는 output은 chi-square test를 통해 uniform 분포를 따르는것으로 검증됬고, Wald-Wolfowitz runs test와 von Neumann Rank test와 serial correlation로 무작위성이 검증되었다.

향후에는 benchmarking을 통해 get_rand_int() 함수의 성능을 더 향상 시키고 싶고, 위 사용한 방법이 아닌 다른 방법이 있는지 조사를 하고 싶다.

References

[1] McHugh, ML. The chi-square test of independence. Biochem Med (Zagreb). 2013;23(2):143-9.
[2] C. Heschl, William. An Investigation of the Power of the Wald-Wolfowitz, Two Sample, Runs Test. 1971;190.
[3] Bartels, R. The rank version of von Neumann’s ratio test for randomness, Journal of the American Statistical Association, vol.77, pp.40-46.

LS0tCnRpdGxlOiAiUmFuZG9tIEludGVnZXIgR2VuZXJhdG9yIFVzaW5nIGEgQmluYXJ5IEludGVnZXIgR2VuZXJhdG9yIgphdXRob3I6ICJFdWdlbmUgQ2hhIgpkYXRlOiAiTWFyY2ggMSwgMjAxOSIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKCmBgYHtyLCBlY2hvID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KbGlicmFyeSgndGlkeXZlcnNlJykKbGlicmFyeSgnZ2dwbG90MicpCmxpYnJhcnkoJ0VudlN0YXRzJykKbGlicmFyeSgnbGF3c3RhdCcpCmxpYnJhcnkoJ2RhdGEudGFibGUnKQpsaWJyYXJ5KCdjb3JycGxvdCcpCmxpYnJhcnkoJ0htaXNjJykKbGlicmFyeSgncmFuZHRlc3RzJykKbGlicmFyeSgnRGVzY1Rvb2xzJykKbGlicmFyeSgnUi5vbycpCgpvcHRpb25zKHNjaXBlbiA9IDk5OSkKYGBgCgojIyBQcm9ibGVtIAow6rO8IDHsnYQg66as7YS07ZWY64qUIO2VqOyImCBnZXRfcmFuZG9tX2JpbmFyeSgp6rCAIOyeiOyKteuLiOuLpC4KCuydtCDtlajsiJjripQg64uk7J2M6rO8IOqwmeydtCDsnbTrr7gg7KCV7J2YIOuQmOyWtCDsnojsirXri4jri6QuICAKKipQeXRob246KioKYGBge3B5dGhvbn0KZnJvbSByYW5kb20gaW1wb3J0IHJhbmRyYW5nZQpkZWYgZ2V0X3JhbmRvbV9iaW5hcnkoKToKCXJldHVybiByYW5kcmFuZ2UoMikKYGBgCgoqKlI6KioKYGBge3J9CmdldF9yYW5kb21fYmluYXJ5IDwtIGZ1bmN0aW9uKCl7CiAgc2FtcGxlKDA6MSwxKQp9CmBgYAoK7J20IO2VqOyImOunjOydhCDsnbTsmqntlZjsl6wgMOqzvCDso7zslrTsp4Qgbi0x6rmM7KeA7J2YIOuenOuNpOqwkuydhCDrpqzthLTtlZjripQg7ZWo7IiYZ2V0X3JhbmRfaW50KG4p7J2EIOq1rO2YhO2VmOyEuOyalC4KCgoqKuyYiOygnCoqCmBgYHtudWxsLCByZXN1bHRzID0gJ2hpZGUnfQrsi6Ttlok6IGdldF9yYW5kX2ludCgxMikK6rKw6rO8OiAwIG9yIDEgb3IgMiBvciAzIG9yIDQuLi4gb3IgMTEKYGBgCgoqKuygnOyVveyCrO2VrSoqIDogUHl0aG9uLCBSIOuRkOqwgOyngCDslrjslrTspJEg7ZWY64KY66GcIOq1rO2YhO2VqeuLiOuLpC4gCgpSIE1hcmtkb3du7J2064KYIEp1cHl0ZXIgbm90ZWJvb2vsnLzroZwg7JWE7J2065SU7Ja067aA7YSwIOq1rO2YhOyXkOyEnCDsi6Ttl5gsIO2FjOyKpO2KuCwg6rKw6rO86rmM7KeAIOygleumrO2VtOyEnCDsoJzstpztlbTslbwg7ZWp64uI64ukLiDsi5zqsIHtmZTrgpgg7Ya16rOE6rKA7Kad7J2EIOychO2VnCDrnbzsnbTruIzrn6zrpqzrk7HsnZgg7Yyo7YKk7KeA64qUIOyekOycoOuhreqyjCDsgqzsmqntlZjshZTrj4Qg65Cp64uI64ukLihnZ3Bsb3QsIG1hdHBsb3RsaWIsIHNlYWJyb24sIHNjaXB54oCmKSDtlZjsp4Drp4wg64K07J6l65CcIOuenOuNpCDtlajsiJjripQg7IKs7Jqp7ZWY7Iuc66m0IOyViOuQqeuLiOuLpC4KPGJyPgoKIyMgU29sdXRpb24KCuusuOygnCDtkoDsnbQg7KCR6re8IOuwqeuyleydgCBnZXRfcmFuZF9pbnQoKeulvCDsnbTsmqntlbQg7J207KeE7IiY66W8IOyDneyEse2VmOqzoCwg7J207KeE7IiY66W8IOyLreynhOyImOuhnCDrsJTqvrjqs6AsIOyDneyEseuQmOuKlCDsi63sp4TsiJjqsIAg7JuQ7ZWY64qUIOyIq+yekCBu67O064ukIO2BtCDqsr3smrAg64uk7IucIOydtOynhOyImOulvCDsg53shLEg7ZWc64ukLgoK7KCI7LCo64qUIOuLpOydjOqzvCDqsJnsirXri4jri6Q6CgojIyMgUHJvY2VzcwoqKlN0ZXAgMToqKiAgCjJea14gPiBuIOyXkOyEnCDqsIDriqXtlZwg6rCA7J6lIOyekeydgCBr66W8IOywvuuKlOuLpAoKKipTdGVwIDI6KiogIApr6ri47J207J2YIGxpc3Trpbwg7IOd7ISx7ZWc64ukCgoqKlN0ZXAgMzoqKiAgCmxpc3TrpbwgZ2V0X3JhbmRvbV9iaW5hcnkoKSDtlajsiJjrpbwg7Ya17ZW0IOyDneyEseuQmOuKlCAwIOuYkOuKlCAx66GcIOyxhOyatOuLpAoKKipTdGVwIDQ6KiogIArsg53shLHrkJwg7J207KeEIOuCnOyImOulvCDsi63sp4TsiJjroZwg67CU6r6864ukCgoqKlN0ZXAgNToqKiAgCuyLreynhOyImCBvdXRwdXTsnbQgbiDrs7Tri6Qg7YG0IOqyveyasCwg7JyEIFN0ZXAgM+yZgCBTdGVwIDTrpbwg67CY67O17ZWc64ukCgo8Y2VudGVyPgohW10oMTkwMjIzX3BuZ19maWd1cmUxLnBuZykKPC9jZW50ZXI+Cgo8YnI+CgojIyMgQ29kZQoqKmdldF9yYW5kb21fYmluYXJ5IO2VqOyImCoqICAK66y47KCc7JeQ7IScIOyjvOyWtOynhCDtlajsiJguIHVuaWZvcm0g67aE7Y+s7JeQIOuUsOudvCAwIOuYkOuKlCAx7J2EIOyDneyEse2VnOuLpC4KYGBge3J9CmdldF9yYW5kb21fYmluYXJ5IDwtIGZ1bmN0aW9uKCl7CiAgc2FtcGxlKDA6MSwxKQp9CmdldF9yYW5kb21fYmluYXJ5KCkKYGBgCgoqKmJpbjJpbnQg7ZWo7IiYKiogIArsnbTsp4TsiJjrpbwg7Iut7KeE7IiY66GcIOuwlOq+uOuKlCDtlajsiJjri6QuIApgYGB7cn0KYmluMmludCA8LSBmdW5jdGlvbih4KXsKICBpZighaXMubnVtZXJpYyh4KSl7CiAgICB0aHJvdygiT25seSBudW1lcmljIGlucHV0cyBhcmUgYWxsb3dlZCIpCiAgfQogIAogIHggJT4lIAogIGFzLmNoYXJhY3RlcigpICU+JSAgICMg7J207KeE7IiY66W8IHN0cmluZ+ycvOuhnCDrs4DtmZggCiAgc3RyX3NwbGl0KCIiKSAlPiUgICAgIyBzdHJpbmfsnZgg6rCBIOyalOyGjOulvCDrtoTrpqwgCiAgdW5saXN0KCkgJT4lICAgICAgICAgIyBsaXN066W8IHZlY3RvcuuhnCDrs4DtmZgKICB7cmV2KC4gPT0gMSl9ICU+JSAgICAjIO2bhCDqs4TsgrDsnYQg7JyE7ZW0IOyInOyEnOulvCDrsJTqvrjqs6AgYm9vbGVhbuycvOuhnCDrs4DtmZgKICAgICAgICAgICAgICAgICAgICAgICAjIHt966GcIOyghCDri6jqs4TsnZggb3V0cHV07J2EIGV2YWx1YXRpb24g7ZWc64ukCiAgd2hpY2goKSAlPiUgICAgICAgICAgIyBUUlVF7J24IGluZGV466W8IOywvuuKlOuLpC4g7J207KeE7IiY7J2YIOyekOumv+yImCDsnbTri6QKICB7Ml4oLi0xKX0gJT4lICAgICAgICAjIDIqKuyekOumv+yImOulvCDqs4TsgrDtlbQg7Iut7KeE7IiY66GcIOuzgO2ZmAogIHN1bSgpICAgICAgICAgICAgICAgICMg7ZWp7J2EIOq1rO2VnOuLpAp9CiNiaW4yaW50KCIxMDAxMDEwMTAxIikKYmluMmludCgxMDAxMDExMDEwMTExMTEpCmBgYAoKKipnZXRfcmFuZF9pbnQg7ZWo7IiYKiogIArrrLjsoJzsl5DshJwg7KO87Ja07KeEIGdldF9yYW5kb21fYmluYXJ5KCnrpbwg7J207Jqp7ZWcIOuCnOyImCDsg53shLEg7ZWo7IiY64ukLgpgYGB7cn0KZ2V0X3JhbmRfaW50IDwtIGZ1bmN0aW9uKG4pewogIGlmKG4gPT0gMCl7CiAgICB0aHJvdygiMCBpcyBvdXRzaWRlIHRoZSBhbGxvd2VkIHN1YnNldCIpCiAgfSBlbHNlIGlmICghaXMubnVtZXJpYyhuKSl7CiAgICB0aHJvdygiT25seSBudW1lcmljIGlucHV0cyBhcmUgYWxsb3dlZCIpCiAgfSBlbHNlIGlmIChuID09IDEpIHsKICAgIDAKICB9IGVsc2UgewogICAgeCA8LSBuIC0gMSAgICAgICAgICAgICAgICAgICAgICAgICAjIG4tMSDsoIDsnqXtlZjquLAKICAgIGsgPC0gMCAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFN0ZXAgMTog7J207KeE7IiY7J2YIOq4uOydtCBrIOq1rO2VmOq4sAogICAgd2hpbGUoeC8yKiprID4gMSl7CiAgICAgayA9IGsgKyAxCiAgICB9CiAgICAKICAgIGxpc3QgPC0gc2VxX2xlbihrKSAgICAgICAgICAgICAgICAgICAgICAjIFN0ZXAgMjoga+q4uOydtOydmCBsaXN0IOyDneyEsSAKICAgIG91dF9pbnQgPC0gbiAgICAgICAgICAgICAgICAgICAgICAKICAgIHdoaWxlKG91dF9pbnQgPiB4KXsgICAgICAgICAgICAgICAjIFN0ZXAgMywgNCwgNTogd2hpbGXsnYQg7J207Jqp7ZWcIOuCnOyImCDsg53shLEKICAgICAgb3V0X2ludCA8LSAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICBzYXBwbHkobGlzdCwgCiAgICAgICAgICAgICAgIGZ1bmN0aW9uKHkpIHkgPSBnZXRfcmFuZG9tX2JpbmFyeSgpKSAlPiUgIyBTdGVwIDM6IGxpc3TrpbwgMCwx66GcIOyxhOybgAogICAgICAgIHthcy5udW1lcmljKHBhc3RlKC4sIGNvbGxhcHNlID0gIiIpKX0gJT4lICAgICAgICMgU3RlcCAzOiDsnbTsp4TsiJgg7IOd7ISxCiAgICAgICAgYmluMmludCgpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBTdGVwIDQ6IOydtOynhOyImOulvCDsi63sp4TsiJjrnbwg67CU6r6864ukCiAgICB9CiAgICBvdXRfaW50CiAgfQp9CiNnZXRfcmFuZF9pbnQoMCkKI2dldF9yYW5kX2ludCgxKQojZ2V0X3JhbmRfaW50KCIxMiIpCmdldF9yYW5kX2ludCgxMikKYGBgCjxicj4KCiMjIFRlc3QKCiMjIyBFeHBsb3JhdG9yeSBEYXRhIEFuYWx5c2lzCgoqKnNhbXBsZV9mdW4g7ZWo7IiYKioKZ2V0X3JhbmRfaW50KCkg7ZWo7IiY66W8IOydtOyaqe2VtCBzYW1wbGluZ+ydhCDtlZzri6QuIG5zaW3snYAgc2FtcGxpbmcg7Zqf7IiY7J206rOgLCBu7J2AIGdldF9yYW50X2ludChuKeydmCBu7J2064ukLgpgYGB7cn0Kc2FtcGxlX2Z1biA8LSBmdW5jdGlvbihuc2ltLCBuKXsKICBsaXN0IDwtIG51bWVyaWMobnNpbSkKICBvdXQgPC0gc2FwcGx5KGxpc3QsIGZ1bmN0aW9uKHgpIHggPSBnZXRfcmFuZF9pbnQobikpCiAgb3V0Cn0KYGBgCjxicj4Kbj0xMuydtOudvOuKlCDqsIDsoJXtlZjsl5AsIGdldF9yYW5kX2ludCgpIHNhbXBsaW5n7J2EIDEwMCwwMDDrsogg7Iuc64+E7ZWc64ukCmBgYHtyfQpkZiA8LSBzYW1wbGVfZnVuKG5zaW0gPSAxMDAwMDAsIG4gPSAxMikKZGYgPC0gZGF0YS5mcmFtZShkZikKaGVhZChkZiwgMTApCmBgYAo8YnI+CuqwgSDsiKvsnpDqsIAg66qH67KIIOyDneyEseydtCDrkKzripTsp4Ag7JWM7JWE67O07J6QLgpgYGB7cn0KdGFibGUoZGYpCmBgYAo8YnI+CjAg7JeQ7IScIDEx7J20IOyDneyEseycvOuhnCDsnbjtlbQg64uo7IicIO2Pieq3oOydgCA1LjXsmYAg7Ja064qQ7KCV64+EIOu5hOyKt+2VtOyVvO2VnOuLpC4KYGBge3J9CmRmICU+JSAKICBwbHlyOjpzdW1tYXJpemUobWVhbiA9IG1lYW4oZGYpKQpgYGAKPGJyPgrsg53shLHrkJwg7J6Q66OM7J2YIO2Pieq3oCA1LjUxIOydgCA1LjUw7JmAIOu5hOyKt+2VmOuLpC4KPGJyPiAgCmdncGxvdOydhCDsnbTsmqntlbQgdW5pZm9ybSBkaXN0cmlidXRpb27snbgg6rKDIOqwmeydgOyngCDsgrTtjrTrs7jri6QuCmBgYHtyfQpnZ3Bsb3QoZGYsIGFlcyh4ID0gZGYpKSArCiAgZ2VvbV9oaXN0b2dyYW0oYmlud2lkdGggPSAxKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICB5bGFiKCLrsJjrs7Ug7Zqf7IiYIikgKwogIHRoZW1lX3NldCh0aGVtZV9ncmF5KGJhc2VfZmFtaWx5PSJBcHBsZUdvdGhpYyIpKSArCiAgdGhlbWUoYXhpcy50aXRsZS54ID0gZWxlbWVudF9ibGFuaygpKSArCiAgc2NhbGVfeF9kaXNjcmV0ZShsaW1pdHMgPSAwOjExKQpgYGAKPGNlbnRlcj48Zm9udCBzaXplID0gND4KKipGaWd1cmUgMioqLiDrgpzsiJgg7IOd7ISxIDEw66eM67KIIOuwmOuztSDqsrDqs7wKPC9mb250PjwvY2VudGVyPgo8YnI+CuuztOuLpOyLnO2UvCB1bmlmb3JtIGRpc3RyaWJ1dGlvbuyduOqygyDsspjrn7wg67O07J207KeA66eMIO2GteqzhOyggSDqsoDspp3snbQg7ZWE7JqU7ZWY64ukLgo8YnI+CgojIyMgU3RhdGlzdGljYWwgVGVzdGluZwo+7Ja065ag7ZWcIOyCrOuejOydtOuToCDsl7DsgrDsoIHsnbgg67Cp67KV7Jy866GcIOuCnOyImCDsg53shLHsnYQg6rOg66CkIO2VmOuKlCDsnpDripQg64u57Jew7Z6IIOyjhOydmCDsg4Htg5zsl5Ag7J2066W066CA64ukLi4uIOuCnOyImCDsg53shLHsnbTrnbzripQg6rKD7J2AIOyXhuuLpC4g6re47KCAIOuCnOyImCDsg53shLHtlZjripQg67KV66eMIOyeiOydhCDrv5DsnbTri6QuIOyasOumrOuKlCDri6jsiJztnogg7Iir7J6Q66W8IOunjOuTnOuKlCDsmpTrpqwg66CI7Iuc7ZS866W8IOuLpOujsCDrv5DsnbTri6QuICAKLSAqTW9udGUgQ2FybG8gTWV0aG9kKiAoMTk1MSksIEpvaG4gdm9uIE5ldW1hbm4KCuyasOumrOqwgCDsg53shLHtlZwg64Kc7IiY64qUIOyXsOyCsCDrsKnrspXsnLzroZwg6rWs7ZWcIOydmOyCrCDrgpzsiJjsnbTquLDsl5Ag7Ya16rOE7KCB7Jy866GcIOqygOymneydhCDtlbTslbztlZzri6QuIO2VqOyImOyXkOyEnCDsg53shLHrkJwg7J6Q66OM6rCAIOuCnOyImOyduOyngOulvCDtmZXsi6TtlZjqsowg7JWM66Ck66m0IOuLpOydjCDrkZDqsIDsp4Ag7KGw6rG07J20IOy2qeyhseuQmOyVvO2VnOuLpDogIAoxLiDthrXqs4TsoIHsnLzroZwg7Jyg7J2Y7ZWcIOyImOykgOyXkOyEnCB1bmlmb3JtIOu2hO2PrOulvCDrlLDrpbjripTsp4AgIAoyLiDsiKvsnpDqsITsl5Ag7IOB6rSA6rSA6rOE6rCAIOyeiOuKlOyngAoK7IOd7ISx65CcIOyekOujjOuKlCDsoJXqt5wg67aE7Y+s66W8IOuUsOultOyngCDslYrsnLzrr4DroZwsIOu5hOuqqOyImOyggSDthrXqs4TsoIHsnbgg6rKA7KadIOuwqeuyleydhCDshLjqsIDsp4Ag7Iuc64+E7ZW067O464ukOiAgCjEuIOyekOujjOydmCDsmIjsg4Eg67CPIOq0gOy4oeuQnCDruYjrj4TroZwgY2hpLXNxdWFyZSBnb29kbmVzcyBvZiBmaXQgdGVzdOulvCDsnbTsmqntlZwgdW5pZm9ybSBkaXN0cmlidXRpb24g6rKA7KadLiAgCjIuIOyDneyEseuQnCDsiJjqsITsnZgg64+F66a97ISx7J2EIOqygOymne2VmOuKlCBXYWxkLVdvbGZvd2l0eiBydW5zIHRlc3QuICAKMy4g7IOd7ISx65CcIOyImOydmCDqs4Tsl7Qg7IOB6rSAIOqygOymnSAoc2VyaWFsIGNvcnJlbGF0aW9uIHRlc3QpLiAgCgrsnIQg7IS46rCA7KeAIOqygOygleydgCDrgrTrtoDsoIHsnbgg64Kc7IiYIOyDneyEsSDtlajsiJjrpbwg7JOw7KeAIOyViuycvOuvgOuhnCDsoJzslb0g7KGw6rG07J2EIOy2qeyhse2VnOuLpC4KCiMjIyMgQ2hpLXNxdWFyZSBHb29kbmVzcyBvZiBGaXQgVGVzdArrgpzsiJgg7IOd7ISx7J20IHVuaWZvcm0g67aE7Y+s66W8IOuUsOulvOyLnCDsmIjsuKEg65CY64qUIOu5iOuPhOyZgCDqtIDsuKHrkJwg67mI64+E66W8IOu5hOq1kO2VtCBjaGktc3F1YXJlIHRlc3Trpbwg7Ya17ZW0IOuRkCDtkZzrs7jsnbQg64uk66W47KeA66W8IOqygOymne2VnOuLpC4KCiQkSF9vOiDsg53shLHrkJxcO+yImOydmFw77JiI7IOBXDvruYjrj4TsmYBcO+q0gOy4oVw767mI64+E6rCAXDvqsJnri6QkJAokJEhfYTog7IOd7ISx65CcXDvsiJjsnZhcO+yYiOyDgVw767mI64+E7JmAXDvqtIDsuKFcO+u5iOuPhOqwgFw76rCZ7KeAXDvslYrri6QkJApgYGB7cn0KZGZfY2hpIDwtIGNiaW5kKG9ic2VydmVkID0gdGFibGUoZGYpLAogICAgICAgICAgICAgICAgZXhwZWN0ZWQgPSAxMDAwMDAvMTIpCmRmX2NoaQpjaGlzcS50ZXN0KGRmX2NoaSkKYGBgCnAtdmFsdWUgMC45ODk27J2AIOycoOydmCDsiJjspIAgMC4wNeuztOuLpCDtmITsoIDtnogg7YGs6riwIOuVjOusuOyXkCDqt4DrrLTqsIDshKTsnYQg7LGE7YOd7ZWY6rOgIOyDneyEseuQnCDrgpzsiJjrk6TsnZgg7JiI7LihIOu5iOuPhOyZgCDqtIDsuKEg67mI64+E6rCAIOqwmeuLpOqzoCDtjJDri6jsnYQg64K066aw64ukLiDspokgY2hpLXNxdWFyZSB0ZXN0IGZvciBpbmRlcGVuZGVuY2Xrpbwg7Ya17ZW0IHVuaWZvcm1pdHnripQg7KO87J6lIO2VoCDsiJgg7J6I7KeA66eMLCDrrLTsnpHsnITshLHsnYQg6rKA7Kad7ZWY6riw7JeQ64qUIO2GteqzhOyggSDqsoDspp3roKXsnbQg64uk66W4IOuwqeuyleyXkCDruYTtlbQg64Ku64uk6rOgIOyVjOugpOyguOyeiOqzoFsxXSDsiKvsnpDqsITsl5Ag7Yq466CM65Oc6rCAIOyeiOuKlOyngOulvCDtjJDri6gg7ZWgIOyImCDsl4bri6QuIOunjOyVvSDtirjroIzrk5zqsIAg7J6I64uk66m0IOustOyekeychOyEseydhCDso7zsnqUg7ZWgIOyImCDsl4bri6QuCgojIyMjIFdhbGQtV29sZm93aXR6IFJ1bnMgVGVzdAoK64uk7J2M7J2AIFdhbGQtV29sZm93aXR6IFJ1bnMgVGVzdOulvCDsgrTtjrTrs7TsnpAuIGNoaS1zcXVhcmUgdGVzdOuztOuLpOuKlCDthrXqs4TsoIEg6rKA7KCV66Cl7J20IOuGkuq4sOuhnCDslYzroKTsoLgg7J6I6rOgWzJdLCDtirjroIzrk5zrpbwg6rKA7Kad7ZWgIOyImCDsnojripQg7J6l7KCQ7J20IOyeiOuLpC4g64uk7J2M7IiY6rCAIOyghOyImOuztOuLpCDtgbQg6rK97JqwICssIOyekeydhCDqsr3smrAgLeuhnO2VmOqzoCDrqqjrk6Ag7IiY66W8IOqzhOyCsO2VnOuLpC4gK+yZgCAt7J2YIOyhsO2VqeydmCDrqqjrk6Ag6rK97Jqw7J2YIOyImOulvCDqs4TsgrDtlZjqs6Ag7KGw7ZWpIOqygOygleydhCDtlZzri6QuCgokJEhfbzog7IOd7ISx65CcXDvsi5ztgIDsiqTripRcO+ustOyekeychOuhnFw77IOd7ISx65CQ64ukJCQKJCRIX2E6IOyDneyEseuQnFw77Iuc7YCA7Iqk64qUXDvrrLTsnpHsnITroZxcO+yDneyEseuQmOyngFw77JWK7JWY64ukJCQKYGBge3J9CnJ1bnMudGVzdChkZiRkZikKYGBgCnAtdmFsdWXsnbggMC41ODgy64qUIOycoOydmOyImOykgCAwLjA167O064ukIOuGkuydgCDqsoPsnLzroZwg67O07JWEIOq3gOustOqwgOyEpOydhCDssYTtg53tlZjqs6Ag7IOd7ISx65CcIOyekOujjOydmCDrrLTsnpHsnITshLHsnYQg67Cb7JWE65Ok7J28IOyImCDsnojri6QuIAoKIyMjIyBTZXJpYWwgQ29ycmVsYXRpb24gVGVzdAoK7Yq57KCV7ZWcIOqyveyasOyXkOuKlCB2b24gTmV1bWFubiByYW5rIHRlc3TqsIAgcnVucyB0ZXN067O064ukIOubsOyWtOuCmOuLpOqzoCDslYzroKTsoLgg7J6I7Jy866+A66GcWzNdIOuniOyngOunieycvOuhnCByYW5rIHRlc3TroZwg66y07J6R7JyE7ISx7J2EIOqygOymnSDtlbTrs7TsnpAuIOyXsOyGjeyggeycvOuhnCDsnbTslrTsp4DripQg7Iir7J6Q65Ok7J2YIOyDgeq0gCDqs4TsiJggJFxyaG9fMSTrpbwg6rOE7IKw7ZWc64ukLgokJEhfbzogXHJob18xID0gMCQkCiQkSF9hOiBccmhvXzEgXG5lcSAxJCQKCmBgYHtyfQpCYXJ0ZWxzUmFua1Rlc3QoZGYkZGYsYWx0ZXJuYXRpdmUgPSAidHJlbmQiKQpgYGAKcC12YWx1ZeuKlCAwLjgyOeuhnCwg7Jyg7J2Y7IiY7KSA7J24IDAuMDXrs7Tri6Qg7JuU65Ox7Z6IIOuGkuuLpC4g7ZiE7J6s7J2YIOyekOujjOyXkOyEnOuKlCDsiKvsnpDsmYAg7KCE7Iir7J6Q7J2YIGxhZ+yduCBrID0gMOydvCDqsr3smrDsmYAgbGFnIGsgPSAx7J28IOqyveyasOydmCDrtoTtj6zripQg7J2Y7KG064+E6rCAIOyXhuuKlCDqsoPsnLzroZwg7YyQ64uoIO2VoOyImCDsnojsp4Drp4wsIGxhZyBrID0gMTAwIOq5jOyngOulvCDqs4TsgrDsnYQg7ZWY7J6QLiDsnbTrpbwg7ZWY6riwIOychO2VtOyEoCDsl7DsgrDsnbQg6rCE7Y647ZWcIOqzhOyXtCDsg4HqtIDqs4TsiJjrpbwg6rOE7IKw7ZW067O07J6QLiDsg4HqtIDqs4TsiJjqsIAgMOyXkCDqsIDquYzsmrDrqbQg7IiY6rCAIOustOyekeychOuhnCDsg53shLHsnbQg65Cs64uk6rOgIO2MkOuLqOydhCDrgrTrprQg7IiYIOyeiOuLpC4KCmBgYHtyfQpkZl9zaGlmdCA8LSBzaGlmdChkZiwgbiA9IDE6MTAwLCBmaWxsID0gZ2V0X3JhbmRfaW50KDEyKSwgdHlwZSA9ICJsYWciKQpkZl9zaGlmdCA8LSBkby5jYWxsKCJjYmluZCIsIGRmX3NoaWZ0KQpkZl9zaGlmdC5jb3IgPC0gY29yKGRmX3NoaWZ0KQpjb3JycGxvdChkZl9zaGlmdC5jb3IsCiAgICAgICAgIHRsLnBvcyA9ICJuIikKYGBgCjxjZW50ZXI+PGZvbnQgc2l6ZSA9ICI0Ij4KKipGaWd1cmUgMyoqLiAgTGFnIGsgPSAxMDDquYzsp4DsnZgg7IOB6rSA6rOE7IiY65Ok7J2YIGNvcnJlbGF0aW9uIO2RnC4gCjwvZm9udD48L2NlbnRlcj4KCmBgYHtyfQphY2YoZGYsIGxhZy5tYXggPSAxMDAwMCwgcGxvdCA9IFRSVUUpCmBgYAoKCjxjZW50ZXI+PGZvbnQgc2l6ZSA9ICI0Ij4KKipGaWd1cmUgNCoqLiAgIGxhZyA9IDEwMDAwIOq5jOyngOydmCBhdXRvLWNvcnJlbGF0aW9uIAo8L2ZvbnQ+PC9jZW50ZXI+Cjxicj4K6rCZ7J2AIO2RnOuzuOqwhOydmCDsg4HqtIDqs4TsiJjripQg64u57Jew7Z6IIDEgKO2MjOuekeyDiSkg7J207KeA66eMLCDtkZzrs7jqsITsnZgg7IOB6rSA6rOE7IiY64qUIOuqqOuRkCAw7J246rKD7Jy866GcIOuztOyXrCwgayA9IDEwMDAw6rmM7KeA64qUIO2RnOuzuOq0gOydmCDsnZjsobTrj4TqsIAg7JeG64qU6rKD7Jy866GcIOuztOqzoCwg7IOd7ISx65CcIOyekOujjOydmCDrrLTsnpHsnITshLHsnYQg7J6F7KadIO2VoCDsiJgg7J6I64ukLgoKIyMgQ29uY2x1c2lvbgoKZ2V0X3JhbmRvbV9iaW5hcnkoKeulvCDthrXtlbQg66eM65OgIGdldF9yYW5kX2ludCgpIO2VqOyImOulvCDrp4zrk6Tsl4jqs6AsIGdldF9yYW5kX2ludCgp7JeQ7IScIOuCmOyYpOuKlCBvdXRwdXTsnYAgY2hpLXNxdWFyZSB0ZXN066W8IO2Gte2VtCB1bmlmb3JtIOu2hO2PrOulvCDrlLDrpbTripTqsoPsnLzroZwg6rKA7Kad65Cs6rOgLCBXYWxkLVdvbGZvd2l0eiBydW5zIHRlc3TsmYAgdm9uIE5ldW1hbm4gUmFuayB0ZXN07JmAIHNlcmlhbCBjb3JyZWxhdGlvbuuhnCDrrLTsnpHsnITshLHsnbQg6rKA7Kad65CY7JeI64ukLgoK7Zal7ZuE7JeQ64qUIGJlbmNobWFya2luZ+ydhCDthrXtlbQgZ2V0X3JhbmRfaW50KCkg7ZWo7IiY7J2YIOyEseuKpeydhCDrjZQg7Zal7IOBIOyLnO2CpOqzoCDsi7bqs6AsIOychCDsgqzsmqntlZwg67Cp67KV7J20IOyVhOuLjCDri6Trpbgg67Cp67KV7J20IOyeiOuKlOyngCDsobDsgqzrpbwg7ZWY6rOgIOyLtuuLpC4KCjxicj4KCiMjIyMgUmVmZXJlbmNlcwpbMV0gTWNIdWdoLCBNTC4gW1RoZSBjaGktc3F1YXJlIHRlc3Qgb2YgaW5kZXBlbmRlbmNlXShodHRwczovL3d3dy5uY2JpLm5sbS5uaWguZ292L3BtYy9hcnRpY2xlcy9QTUMzOTAwMDU4LykuIEJpb2NoZW0gTWVkIChaYWdyZWIpLiAyMDEzOzIzKDIpOjE0My05Lgo8YnI+ClsyXSBDLiBIZXNjaGwsIFdpbGxpYW0uIFtBbiBJbnZlc3RpZ2F0aW9uIG9mIHRoZSBQb3dlciBvZiB0aGUgV2FsZC1Xb2xmb3dpdHosIFR3byBTYW1wbGUsIFJ1bnMgVGVzdF0oaHR0cHM6Ly9hcHBzLmR0aWMubWlsL2R0aWMvdHIvZnVsbHRleHQvdTIvNzQzMDc4LnBkZikuIDE5NzE7MTkwLgo8YnI+ClszXSBCYXJ0ZWxzLCBSLiBbVGhlIHJhbmsgdmVyc2lvbiBvZiB2b24gTmV1bWFubuKAmXMgcmF0aW8gdGVzdCBmb3IgcmFuZG9tbmVzc10oaHR0cHM6Ly93d3cucmVzZWFyY2hnYXRlLm5ldC9wdWJsaWNhdGlvbi8yMzA2Mzk5NTFfVGhlX1JhbmtfVmVyc2lvbl9vZl92b25fTmV1bWFubidzX1JhdGlvX1Rlc3RfZm9yX1JhbmRvbW5lc3MpLCBKb3VybmFsIG9mIHRoZSBBbWVyaWNhbiBTdGF0aXN0aWNhbCBBc3NvY2lhdGlvbiwgdm9sLjc3LCBwcC40MC00Ni4gCgo=