Introduction

In this document, we’ll explore the basics of neural networks and deep learning. We’ll visualize a simple neural network with 3 input nodes, a hidden layer with 3 nodes, and an output layer with 2 nodes. We will also demonstrate a basic feedforward pass and a backpropagation process to illustrate the core concepts.

Neural Networks and Deep Learning

Deep learning is a subset of machine learning that involves neural networks with multiple layers, known as deep neural networks. Neural networks are composed of neurons (or nodes) organized in layers:

  1. Input Layer: Receives the input data.
  2. Hidden Layer: Performs computations and feature transformations.
  3. Output Layer: Produces the final prediction.
# Install and load required libraries
if (!require('DiagrammeR')) install.packages('DiagrammeR', dependencies=TRUE)
library(DiagrammeR)

# Function to draw the neural network graph
draw_neural_network <- function() {
  grViz("
  digraph G {
    rankdir=LR;
    
    node [shape=circle, fontname=Arial, fontsize=10];
    
    # Input Layer
    subgraph cluster_input {
      label = \"Input Layer\";
      I1 [label=\"Input 1\"];
      I2 [label=\"Input 2\"];
      I3 [label=\"Input 3\"];
      color=none;
    }
    
    # Hidden Layer
    subgraph cluster_hidden {
      label = \"Hidden Layer\";
      H1 [label=\"Hidden 1\"];
      H2 [label=\"Hidden 2\"];
      H3 [label=\"Hidden 3\"];
      color=none;
    }
    
    # Output Layer
    subgraph cluster_output {
      label = \"Output Layer\";
      O1 [label=\"Output 1\"];
      O2 [label=\"Output 2\"];
      color=none;
    }
    
    # Connect Input Layer to Hidden Layer
    I1 -> H1;
    I1 -> H2;
    I1 -> H3;
    I2 -> H1;
    I2 -> H2;
    I2 -> H3;
    I3 -> H1;
    I3 -> H2;
    I3 -> H3;
    
    # Connect Hidden Layer to Output Layer
    H1 -> O1;
    H1 -> O2;
    H2 -> O1;
    H2 -> O2;
    H3 -> O1;
    H3 -> O2;
  }
  ")
}

# Draw the neural network graph
draw_neural_network()

The Sigmoid Activation Function and Its Derivative

Sigmoid Activation Function The sigmoid activation function is a widely-used nonlinear activation function in neural networks, especially for binary classification problems. It maps the input values to the (0, 1) range, which is particularly useful for models where the output is expected to be a probability.

Mathematically, the sigmoid function σ(x) is defined as:

\[σ(x) = \frac{1}{1 + e^{-x}}\]

Here, ( x ) can be any real-valued number, and ( e ) is the base of the natural logarithm (approximately 2.71828). The function outputs values between 0 and 1, making it suitable for producing probabilities.

The sigmoid function has a characteristic “S” shaped curve (hence the name “sigmoid”), which smoothly transitions from 0 to 1.

Derivative of the Sigmoid Function The derivative of the sigmoid function, often referred to as ( σ’(x) ), plays a crucial role in backpropagation. It is used to compute the gradient, which helps in updating the weights during training.

The derivative of the sigmoid function is given by:

\[[ σ'(x) = σ(x) \cdot (1 - σ(x)) ]\]

This derivative indicates how steeply the sigmoid curve is changing at any point ( x ). For values of ( x ) far from 0, the sigmoid function’s slope is small, which can lead to the “vanishing gradient” problem. However, near ( x = 0 ), the slope is maximal, which is beneficial for learning.

# Define sigmoid activation function
sigmoid <- function(x) {
  1 / (1 + exp(-x))
}

# Define the derivative of the sigmoid function
sigmoid_derivative <- function(x) {
  x * (1 - x)
}

Initialize Input Features

The input layer of our neural network consists of 3 nodes. We will initialize these input features with random numbers to simulate real-world data.

# Set seed for reproducibility
set.seed(42)

# Initialize input features with random numbers
inputs <- matrix(runif(3, min = 0, max = 1), nrow = 1)

# Print the initialized input features
print("Initialized input features (3 nodes):")
[1] "Initialized input features (3 nodes):"
print(inputs)
         [,1]      [,2]      [,3]
[1,] 0.914806 0.9370754 0.2861395

Initialize Weights

Define the weights between the input layer and the hidden layer, as well as the weights between the hidden layer and the output layer. These weights are initialized with random values.

  1. Input to Hidden Layer Weights: We define a matrix of weights connecting the input layer (with 3 nodes) to the hidden layer (with 4 nodes).
  2. Hidden to Output Layer Weights: We define another matrix of weights connecting the hidden layer (with 4 nodes) to the output layer (with 2 nodes).

Input to Hidden Layer Weights:


\[[ W_{\text{input_hidden}} = \begin{bmatrix} w_{1,1} & w_{1,2} & w_{1,3} & w_{1,4} \\ w_{2,1} & w_{2,2} & w_{2,3} & w_{2,4} \\ w_{3,1} & w_{3,2} & w_{3,3} & w_{3,4} \end{bmatrix} ]\]


Hidden to Output Layer Weights:


\[[ W_{\text{hidden_output}} = \begin{bmatrix} v_{1,1} & v_{1,2} \\ v_{2,1} & v_{2,2} \\ v_{3,1} & v_{3,2} \\ v_{4,1} & v_{4,2} \end{bmatrix} ]\]

# Weights between input layer and hidden layer (3x4)
weights_input_hidden <- matrix(c(
  0.4, 0.1, 0.2, 0.3,
  0.7, 0.5, 0.3, 0.2,
  0.9, 0.6, 0.8, 0.4
), nrow = 3, byrow = TRUE)
print("Weights between input and hidden layer:")
print(weights_input_hidden)

# Weights between hidden layer and output layer (4x2)
weights_hidden_output <- matrix(c(
  0.2, 0.6,
  0.3, 0.5,
  0.7, 0.8,
  0.1, 0.4
), nrow = 4, byrow = TRUE)
print("Weights between hidden and output layer:")
print(weights_hidden_output)

Feedforward Process

The feedforward process in a neural network involves passing the input data through the various layers of the network to produce the output. Here, we describe the steps involved in the feedforward process for our neural network with 3 input nodes, a hidden layer with 3 nodes, and an output layer with 2 nodes.

Step 1: Compute Hidden Layer Inputs

First, we compute the input to the hidden layer by multiplying the input features with the weights connecting the input layer to the hidden layer. Let’s denote the input features as \(\mathbf{X}\) and the weights between the input and hidden layers as \(\mathbf{W_{\text{input\_hidden}}}\).

Mathematically, this can be represented as:

\[ \mathbf{H_{\text{input}}} = \mathbf{X} \times \mathbf{W_{\text{input\_hidden}}} \]

where: - \(\mathbf{X}\) is a 1x3 matrix (input features). - \(\mathbf{W_{\text{input\_hidden}}}\) is a 3x4 matrix (weights between input and hidden layers). - \(\mathbf{H_{\text{input}}}\) will be a 1x4 matrix (input to hidden layer).

# Feedforward process
hidden_input <- inputs %*% weights_input_hidden
hidden_output <- sigmoid(hidden_input)
print("Output of hidden layer (after activation):")
[1] "Output of hidden layer (after activation):"
print(hidden_output)
          [,1]      [,2]      [,3]      [,4]
[1,] 0.9890131 0.9478464 0.9608343 0.8698915

Feedforward Process: Output Layer Computation

In this section, we will compute the input to the output layer and then apply the sigmoid activation function to obtain the final output of the neural network.

Step 3: Compute Input to Output Layer

The inputs to the output layer are computed by performing matrix multiplication between the outputs from the hidden layer and the weights connecting the hidden layer to the output layer.

Mathematically, this is represented as:

\[ \mathbf{Y_{\text{input}}} = \mathbf{H_{\text{output}}} \times \mathbf{W_{\text{hidden\_output}}} \]

where: - \(\mathbf{H_{\text{output}}}\) is the 1x4 matrix of outputs from the hidden layer after the activation function. - \(\mathbf{W_{\text{hidden\_output}}}\) is the 4x2 matrix of weights between the hidden layer and the output layer. - \(\mathbf{Y_{\text{input}}}\) is the resulting 1x2 matrix of inputs to the output layer nodes.

# Compute input to output layer
final_input <- hidden_output %*% weights_hidden_output
final_output <- sigmoid(final_input)
print("Output of final layer (after activation):")
[1] "Output of final layer (after activation):"
print(final_output)
          [,1]      [,2]
[1,] 0.7758649 0.8987994

Assume Expected Output

In order to evaluate the performance of our neural network, we need to compare its predictions to the actual expected output. This process is essential during training, as it provides the basis for calculating errors and subsequently updating the weights through backpropagation.

Defining the Expected Output

For this demonstration, let’s assume the expected output of our neural network. The expected output serves as the ground truth against which we will measure the network’s performance.

The following R code defines a simple expected output matrix. In this example, let’s assume the expected output for our single input example is \([0, 1]\).

# Assume expected output
expected_output <- matrix(c(0, 1), nrow = 1)

print("Assumed expected output:")
[1] "Assumed expected output:"
print(expected_output)
     [,1] [,2]
[1,]    0    1

Calculate Error of the Output

In this step, we calculate the error of the output of the neural network. This error represents the difference between the predicted output generated by the neural network and the expected (ground truth) output. Measuring this error is a critical part of the training process, as it provides the information needed to adjust the network’s weights to improve accuracy.

Error Calculation

The error is computed as the difference between the expected output and the actual output produced by the neural network. Mathematically, this can be represented as:

\[ \text{Error} = \mathbf{Y_{\text{expected}}} - \mathbf{Y_{\text{output}}} \]

where: - \(\mathbf{Y_{\text{expected}}}\) is the matrix of expected (ground truth) outputs. - \(\mathbf{Y_{\text{output}}}\) is the matrix of actual outputs produced by the neural network.

# Calculate error of the output
output_error <- expected_output - final_output
print("Output error:")
[1] "Output error:"
print(output_error)
           [,1]      [,2]
[1,] -0.7758649 0.1012006

Backpropagation Process

In the backpropagation process, we calculate the error and update the weights to minimize this error. This process is essential for training the neural network.

Calculating Delta for the Output Layer

The first step in backpropagation is to compute the delta (gradient) for the output layer. The delta represents the error term adjusted by the derivative of the activation function. For the sigmoid activation function, the derivative is:

\[ σ'(x) = σ(x) \cdot (1 - σ(x)) \]

The delta for the output layer can be computed as:

\[ \delta_{\text{output}} = \text{output\_error} \cdot σ'(\mathbf{Y_{\text{output}}}) \]

where: - \(\text{output\_error}\) is the error of the output computed earlier. - \(σ'(\mathbf{Y_{\text{output}}})\) is the derivative of the sigmoid function applied to the output layer values.

# Define the derivative of the sigmoid function
sigmoid_derivative <- function(x) {
  x * (1 - x)
}

# Calculate the delta for the output layer
d_output <- output_error * sigmoid_derivative(final_output)
print("Delta for the output layer:")
[1] "Delta for the output layer:"
print(d_output)
           [,1]        [,2]
[1,] -0.1349218 0.009205111

Update Weights: Hidden to Output Layer

After calculating the deltas for the output layer in the backpropagation process, we proceed to update the weights connecting the hidden layer to the output layer. The weight update process aims to minimize the error in the network by adjusting the weights based on the calculated deltas.

Weight Update Process

Using the computed deltas (\(\delta_{\text{output}}\)), we adjust the weights between the hidden and output layers. The weight update rule for gradient descent is as follows:

\[ \text{New Weight} = \text{Old Weight} + \eta \cdot (\mathbf{H_{\text{output}}}^T \cdot \delta_{\text{output}}) \]

where: - \(\eta\) is the learning rate, controlling the step size of weight updates. - \(\mathbf{H_{\text{output}}}^T\) is the transpose of the hidden layer output matrix. - \(\delta_{\text{output}}\) is the delta for the output layer.

# Define the learning rate for weight updates
learning_rate <- 0.5

# Update the weights between hidden and output layers
weights_hidden_output <- weights_hidden_output + t(hidden_output) %*% d_output * learning_rate

print("Updated weights between hidden and output layer:")
[1] "Updated weights between hidden and output layer:"
print(weights_hidden_output)
           [,1]      [,2]
[1,] 0.13328030 0.6045520
[2,] 0.23605744 0.5043625
[3,] 0.63518127 0.8044223
[4,] 0.04131635 0.4040037

Conclusion: Interpretation of Output Error

In the neural network context, the “Output error:” matrix conveys the disparities between the predicted output values generated by the network and the actual expected output values. Understanding and analyzing these output errors are fundamental to evaluating the network’s performance and guiding the training process towards optimization.

Analysis of Output Error Values

  • Negative Error (Column 1):
    • The negative value of approximately -0.7758649 suggests an underestimation by the neural network in predicting the corresponding target or class. The larger the magnitude of the negative error, the more significant the underestimation relative to the actual expected output.
  • Positive Error (Column 2):
    • The positive value of around 0.1012006 reveals an overestimation in the network’s predictions for the corresponding target or class. The magnitude of the positive error indicates the degree of overestimation relative to the ground truth.

Insight for Training and Optimization

  • Error Minimization:
    • Minimizing the output error is the main objective during training. Techniques like backpropagation and weight adjustments reduce these errors, aligning the network’s predictions more closely with the expected outputs and improving its overall accuracy.
  • Guiding Network Improvement:
    • Analyzing and monitoring the output error values provides insights into the network’s performance, enabling iterative adjustments to enhance prediction quality. Understanding the error patterns helps in identifying areas for refinement and optimizing the neural network’s learning process.

In conclusion, the interpretation of output error values serves as a metric in assessing the neural network’s predictive performance and refining its accuracy. By minimizing these errors through targeted optimization strategies, the network’s predictive capabilities become more reliable and precise predictions.

LS0tCnRpdGxlOiAiTmV1cmFsIE5ldHdvcmsgRGVtb25zdHJhdGlvbiBhbmQgRGVlcCBMZWFybmluZyBFeHBsYW5hdGlvbiIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQojIyBJbnRyb2R1Y3Rpb24KCkluIHRoaXMgZG9jdW1lbnQsIHdlJ2xsIGV4cGxvcmUgdGhlIGJhc2ljcyBvZiBuZXVyYWwgbmV0d29ya3MgYW5kIGRlZXAgbGVhcm5pbmcuIFdlJ2xsIHZpc3VhbGl6ZSBhIHNpbXBsZSBuZXVyYWwgbmV0d29yayB3aXRoIDMgaW5wdXQgbm9kZXMsIGEgaGlkZGVuIGxheWVyIHdpdGggMyBub2RlcywgYW5kIGFuIG91dHB1dCBsYXllciB3aXRoIDIgbm9kZXMuIFdlIHdpbGwgYWxzbyBkZW1vbnN0cmF0ZSBhIGJhc2ljIGZlZWRmb3J3YXJkIHBhc3MgYW5kIGEgYmFja3Byb3BhZ2F0aW9uIHByb2Nlc3MgdG8gaWxsdXN0cmF0ZSB0aGUgY29yZSBjb25jZXB0cy4KCiMjIE5ldXJhbCBOZXR3b3JrcyBhbmQgRGVlcCBMZWFybmluZwoKRGVlcCBsZWFybmluZyBpcyBhIHN1YnNldCBvZiBtYWNoaW5lIGxlYXJuaW5nIHRoYXQgaW52b2x2ZXMgbmV1cmFsIG5ldHdvcmtzIHdpdGggbXVsdGlwbGUgbGF5ZXJzLCBrbm93biBhcyBkZWVwIG5ldXJhbCBuZXR3b3Jrcy4gTmV1cmFsIG5ldHdvcmtzIGFyZSBjb21wb3NlZCBvZiBuZXVyb25zIChvciBub2Rlcykgb3JnYW5pemVkIGluIGxheWVyczoKCjEuICoqSW5wdXQgTGF5ZXIqKjogUmVjZWl2ZXMgdGhlIGlucHV0IGRhdGEuCjIuICoqSGlkZGVuIExheWVyKio6IFBlcmZvcm1zIGNvbXB1dGF0aW9ucyBhbmQgZmVhdHVyZSB0cmFuc2Zvcm1hdGlvbnMuCjMuICoqT3V0cHV0IExheWVyKio6IFByb2R1Y2VzIHRoZSBmaW5hbCBwcmVkaWN0aW9uLgoKCmBgYHtyfQojIEluc3RhbGwgYW5kIGxvYWQgcmVxdWlyZWQgbGlicmFyaWVzCmlmICghcmVxdWlyZSgnRGlhZ3JhbW1lUicpKSBpbnN0YWxsLnBhY2thZ2VzKCdEaWFncmFtbWVSJywgZGVwZW5kZW5jaWVzPVRSVUUpCmxpYnJhcnkoRGlhZ3JhbW1lUikKCiMgRnVuY3Rpb24gdG8gZHJhdyB0aGUgbmV1cmFsIG5ldHdvcmsgZ3JhcGgKZHJhd19uZXVyYWxfbmV0d29yayA8LSBmdW5jdGlvbigpIHsKICBnclZpeigiCiAgZGlncmFwaCBHIHsKICAgIHJhbmtkaXI9TFI7CiAgICAKICAgIG5vZGUgW3NoYXBlPWNpcmNsZSwgZm9udG5hbWU9QXJpYWwsIGZvbnRzaXplPTEwXTsKICAgIAogICAgIyBJbnB1dCBMYXllcgogICAgc3ViZ3JhcGggY2x1c3Rlcl9pbnB1dCB7CiAgICAgIGxhYmVsID0gXCJJbnB1dCBMYXllclwiOwogICAgICBJMSBbbGFiZWw9XCJJbnB1dCAxXCJdOwogICAgICBJMiBbbGFiZWw9XCJJbnB1dCAyXCJdOwogICAgICBJMyBbbGFiZWw9XCJJbnB1dCAzXCJdOwogICAgICBjb2xvcj1ub25lOwogICAgfQogICAgCiAgICAjIEhpZGRlbiBMYXllcgogICAgc3ViZ3JhcGggY2x1c3Rlcl9oaWRkZW4gewogICAgICBsYWJlbCA9IFwiSGlkZGVuIExheWVyXCI7CiAgICAgIEgxIFtsYWJlbD1cIkhpZGRlbiAxXCJdOwogICAgICBIMiBbbGFiZWw9XCJIaWRkZW4gMlwiXTsKICAgICAgSDMgW2xhYmVsPVwiSGlkZGVuIDNcIl07CiAgICAgIGNvbG9yPW5vbmU7CiAgICB9CiAgICAKICAgICMgT3V0cHV0IExheWVyCiAgICBzdWJncmFwaCBjbHVzdGVyX291dHB1dCB7CiAgICAgIGxhYmVsID0gXCJPdXRwdXQgTGF5ZXJcIjsKICAgICAgTzEgW2xhYmVsPVwiT3V0cHV0IDFcIl07CiAgICAgIE8yIFtsYWJlbD1cIk91dHB1dCAyXCJdOwogICAgICBjb2xvcj1ub25lOwogICAgfQogICAgCiAgICAjIENvbm5lY3QgSW5wdXQgTGF5ZXIgdG8gSGlkZGVuIExheWVyCiAgICBJMSAtPiBIMTsKICAgIEkxIC0+IEgyOwogICAgSTEgLT4gSDM7CiAgICBJMiAtPiBIMTsKICAgIEkyIC0+IEgyOwogICAgSTIgLT4gSDM7CiAgICBJMyAtPiBIMTsKICAgIEkzIC0+IEgyOwogICAgSTMgLT4gSDM7CiAgICAKICAgICMgQ29ubmVjdCBIaWRkZW4gTGF5ZXIgdG8gT3V0cHV0IExheWVyCiAgICBIMSAtPiBPMTsKICAgIEgxIC0+IE8yOwogICAgSDIgLT4gTzE7CiAgICBIMiAtPiBPMjsKICAgIEgzIC0+IE8xOwogICAgSDMgLT4gTzI7CiAgfQogICIpCn0KCiMgRHJhdyB0aGUgbmV1cmFsIG5ldHdvcmsgZ3JhcGgKZHJhd19uZXVyYWxfbmV0d29yaygpCmBgYAojIyBUaGUgU2lnbW9pZCBBY3RpdmF0aW9uIEZ1bmN0aW9uIGFuZCBJdHMgRGVyaXZhdGl2ZQpTaWdtb2lkIEFjdGl2YXRpb24gRnVuY3Rpb24KVGhlIHNpZ21vaWQgYWN0aXZhdGlvbiBmdW5jdGlvbiBpcyBhIHdpZGVseS11c2VkIG5vbmxpbmVhciBhY3RpdmF0aW9uIGZ1bmN0aW9uIGluIG5ldXJhbCBuZXR3b3JrcywgZXNwZWNpYWxseSBmb3IgYmluYXJ5IGNsYXNzaWZpY2F0aW9uIHByb2JsZW1zLiBJdCBtYXBzIHRoZSBpbnB1dCB2YWx1ZXMgdG8gdGhlICgwLCAxKSByYW5nZSwgd2hpY2ggaXMgcGFydGljdWxhcmx5IHVzZWZ1bCBmb3IgbW9kZWxzIHdoZXJlIHRoZSBvdXRwdXQgaXMgZXhwZWN0ZWQgdG8gYmUgYSBwcm9iYWJpbGl0eS4KCk1hdGhlbWF0aWNhbGx5LCB0aGUgc2lnbW9pZCBmdW5jdGlvbiDPgyh4KSBpcyBkZWZpbmVkIGFzOgoKJCTPgyh4KSA9IFxmcmFjezF9ezEgKyBlXnsteH19JCQKCkhlcmUsICggeCApIGNhbiBiZSBhbnkgcmVhbC12YWx1ZWQgbnVtYmVyLCBhbmQgKCBlICkgaXMgdGhlIGJhc2Ugb2YgdGhlIG5hdHVyYWwgbG9nYXJpdGhtIChhcHByb3hpbWF0ZWx5IDIuNzE4MjgpLiBUaGUgZnVuY3Rpb24gb3V0cHV0cyB2YWx1ZXMgYmV0d2VlbiAwIGFuZCAxLCBtYWtpbmcgaXQgc3VpdGFibGUgZm9yIHByb2R1Y2luZyBwcm9iYWJpbGl0aWVzLgoKVGhlIHNpZ21vaWQgZnVuY3Rpb24gaGFzIGEgY2hhcmFjdGVyaXN0aWMgIlMiIHNoYXBlZCBjdXJ2ZSAoaGVuY2UgdGhlIG5hbWUgInNpZ21vaWQiKSwgd2hpY2ggc21vb3RobHkgdHJhbnNpdGlvbnMgZnJvbSAwIHRvIDEuCgpEZXJpdmF0aXZlIG9mIHRoZSBTaWdtb2lkIEZ1bmN0aW9uClRoZSBkZXJpdmF0aXZlIG9mIHRoZSBzaWdtb2lkIGZ1bmN0aW9uLCBvZnRlbiByZWZlcnJlZCB0byBhcyAoIM+DJyh4KSApLCBwbGF5cyBhIGNydWNpYWwgcm9sZSBpbiBiYWNrcHJvcGFnYXRpb24uIEl0IGlzIHVzZWQgdG8gY29tcHV0ZSB0aGUgZ3JhZGllbnQsIHdoaWNoIGhlbHBzIGluIHVwZGF0aW5nIHRoZSB3ZWlnaHRzIGR1cmluZyB0cmFpbmluZy4KClRoZSBkZXJpdmF0aXZlIG9mIHRoZSBzaWdtb2lkIGZ1bmN0aW9uIGlzIGdpdmVuIGJ5OgoKJCRbIM+DJyh4KSA9IM+DKHgpIFxjZG90ICgxIC0gz4MoeCkpIF0kJAoKVGhpcyBkZXJpdmF0aXZlIGluZGljYXRlcyBob3cgc3RlZXBseSB0aGUgc2lnbW9pZCBjdXJ2ZSBpcyBjaGFuZ2luZyBhdCBhbnkgcG9pbnQgKCB4ICkuIEZvciB2YWx1ZXMgb2YgKCB4ICkgZmFyIGZyb20gMCwgdGhlIHNpZ21vaWQgZnVuY3Rpb24ncyBzbG9wZSBpcyBzbWFsbCwgd2hpY2ggY2FuIGxlYWQgdG8gdGhlICJ2YW5pc2hpbmcgZ3JhZGllbnQiIHByb2JsZW0uIEhvd2V2ZXIsIG5lYXIgKCB4ID0gMCApLCB0aGUgc2xvcGUgaXMgbWF4aW1hbCwgd2hpY2ggaXMgYmVuZWZpY2lhbCBmb3IgbGVhcm5pbmcuCgpgYGB7cn0KIyBEZWZpbmUgc2lnbW9pZCBhY3RpdmF0aW9uIGZ1bmN0aW9uCnNpZ21vaWQgPC0gZnVuY3Rpb24oeCkgewogIDEgLyAoMSArIGV4cCgteCkpCn0KCiMgRGVmaW5lIHRoZSBkZXJpdmF0aXZlIG9mIHRoZSBzaWdtb2lkIGZ1bmN0aW9uCnNpZ21vaWRfZGVyaXZhdGl2ZSA8LSBmdW5jdGlvbih4KSB7CiAgeCAqICgxIC0geCkKfQpgYGAKIyMjIEluaXRpYWxpemUgSW5wdXQgRmVhdHVyZXMKClRoZSBpbnB1dCBsYXllciBvZiBvdXIgbmV1cmFsIG5ldHdvcmsgY29uc2lzdHMgb2YgMyBub2Rlcy4gV2Ugd2lsbCBpbml0aWFsaXplIHRoZXNlIGlucHV0IGZlYXR1cmVzIHdpdGggcmFuZG9tIG51bWJlcnMgdG8gc2ltdWxhdGUgcmVhbC13b3JsZCBkYXRhLgoKYGBge3IgaW5wdXQtZmVhdHVyZXMsIGVjaG89VFJVRX0KIyBTZXQgc2VlZCBmb3IgcmVwcm9kdWNpYmlsaXR5CnNldC5zZWVkKDQyKQoKIyBJbml0aWFsaXplIGlucHV0IGZlYXR1cmVzIHdpdGggcmFuZG9tIG51bWJlcnMKaW5wdXRzIDwtIG1hdHJpeChydW5pZigzLCBtaW4gPSAwLCBtYXggPSAxKSwgbnJvdyA9IDEpCgojIFByaW50IHRoZSBpbml0aWFsaXplZCBpbnB1dCBmZWF0dXJlcwpwcmludCgiSW5pdGlhbGl6ZWQgaW5wdXQgZmVhdHVyZXMgKDMgbm9kZXMpOiIpCnByaW50KGlucHV0cykKYGBgCiMjIyBJbml0aWFsaXplIFdlaWdodHMKCkRlZmluZSB0aGUgd2VpZ2h0cyBiZXR3ZWVuIHRoZSBpbnB1dCBsYXllciBhbmQgdGhlIGhpZGRlbiBsYXllciwgYXMgd2VsbCBhcyB0aGUgd2VpZ2h0cyBiZXR3ZWVuIHRoZSBoaWRkZW4gbGF5ZXIgYW5kIHRoZSBvdXRwdXQgbGF5ZXIuIFRoZXNlIHdlaWdodHMgYXJlIGluaXRpYWxpemVkIHdpdGggcmFuZG9tIHZhbHVlcy4KCjEuICoqSW5wdXQgdG8gSGlkZGVuIExheWVyIFdlaWdodHMqKjogV2UgZGVmaW5lIGEgbWF0cml4IG9mIHdlaWdodHMgY29ubmVjdGluZyB0aGUgaW5wdXQgbGF5ZXIgKHdpdGggMyBub2RlcykgdG8gdGhlIGhpZGRlbiBsYXllciAod2l0aCA0IG5vZGVzKS4KMi4gKipIaWRkZW4gdG8gT3V0cHV0IExheWVyIFdlaWdodHMqKjogV2UgZGVmaW5lIGFub3RoZXIgbWF0cml4IG9mIHdlaWdodHMgY29ubmVjdGluZyB0aGUgaGlkZGVuIGxheWVyICh3aXRoIDQgbm9kZXMpIHRvIHRoZSBvdXRwdXQgbGF5ZXIgKHdpdGggMiBub2RlcykuCgo8ZGl2IHN0eWxlPSJ0ZXh0LWFsaWduOiBjZW50ZXI7Ij4KCiMjIyBJbnB1dCB0byBIaWRkZW4gTGF5ZXIgV2VpZ2h0czoKCjwvZGl2Pgo8YnI+CgokJFsKV197XHRleHR7aW5wdXRfaGlkZGVufX0gPQpcYmVnaW57Ym1hdHJpeH0Kd197MSwxfSAmIHdfezEsMn0gJiB3X3sxLDN9ICYgd197MSw0fSBcXAp3X3syLDF9ICYgd197MiwyfSAmIHdfezIsM30gJiB3X3syLDR9IFxcCndfezMsMX0gJiB3X3szLDJ9ICYgd197MywzfSAmIHdfezMsNH0KXGVuZHtibWF0cml4fQpdJCQKCjxicj4KCjxkaXYgc3R5bGU9InRleHQtYWxpZ246IGNlbnRlcjsiPgoKIyMjIEhpZGRlbiB0byBPdXRwdXQgTGF5ZXIgV2VpZ2h0czoKCjwvZGl2Pgo8YnI+CgoKJCRbCldfe1x0ZXh0e2hpZGRlbl9vdXRwdXR9fSA9ClxiZWdpbntibWF0cml4fQp2X3sxLDF9ICYgdl97MSwyfSBcXAp2X3syLDF9ICYgdl97MiwyfSBcXAp2X3szLDF9ICYgdl97MywyfSBcXAp2X3s0LDF9ICYgdl97NCwyfQpcZW5ke2JtYXRyaXh9Cl0kJAoKYGBge3IgaW5pdC13ZWlnaHRzLCBlY2hvPVRSVUV9CiMgV2VpZ2h0cyBiZXR3ZWVuIGlucHV0IGxheWVyIGFuZCBoaWRkZW4gbGF5ZXIgKDN4NCkKd2VpZ2h0c19pbnB1dF9oaWRkZW4gPC0gbWF0cml4KGMoCiAgMC40LCAwLjEsIDAuMiwgMC4zLAogIDAuNywgMC41LCAwLjMsIDAuMiwKICAwLjksIDAuNiwgMC44LCAwLjQKKSwgbnJvdyA9IDMsIGJ5cm93ID0gVFJVRSkKcHJpbnQoIldlaWdodHMgYmV0d2VlbiBpbnB1dCBhbmQgaGlkZGVuIGxheWVyOiIpCnByaW50KHdlaWdodHNfaW5wdXRfaGlkZGVuKQoKIyBXZWlnaHRzIGJldHdlZW4gaGlkZGVuIGxheWVyIGFuZCBvdXRwdXQgbGF5ZXIgKDR4MikKd2VpZ2h0c19oaWRkZW5fb3V0cHV0IDwtIG1hdHJpeChjKAogIDAuMiwgMC42LAogIDAuMywgMC41LAogIDAuNywgMC44LAogIDAuMSwgMC40CiksIG5yb3cgPSA0LCBieXJvdyA9IFRSVUUpCnByaW50KCJXZWlnaHRzIGJldHdlZW4gaGlkZGVuIGFuZCBvdXRwdXQgbGF5ZXI6IikKcHJpbnQod2VpZ2h0c19oaWRkZW5fb3V0cHV0KQoKYGBgCiMjIyBGZWVkZm9yd2FyZCBQcm9jZXNzCgpUaGUgZmVlZGZvcndhcmQgcHJvY2VzcyBpbiBhIG5ldXJhbCBuZXR3b3JrIGludm9sdmVzIHBhc3NpbmcgdGhlIGlucHV0IGRhdGEgdGhyb3VnaCB0aGUgdmFyaW91cyBsYXllcnMgb2YgdGhlIG5ldHdvcmsgdG8gcHJvZHVjZSB0aGUgb3V0cHV0LiBIZXJlLCB3ZSBkZXNjcmliZSB0aGUgc3RlcHMgaW52b2x2ZWQgaW4gdGhlIGZlZWRmb3J3YXJkIHByb2Nlc3MgZm9yIG91ciBuZXVyYWwgbmV0d29yayB3aXRoIDMgaW5wdXQgbm9kZXMsIGEgaGlkZGVuIGxheWVyIHdpdGggMyBub2RlcywgYW5kIGFuIG91dHB1dCBsYXllciB3aXRoIDIgbm9kZXMuCgojIyMjIFN0ZXAgMTogQ29tcHV0ZSBIaWRkZW4gTGF5ZXIgSW5wdXRzCgpGaXJzdCwgd2UgY29tcHV0ZSB0aGUgaW5wdXQgdG8gdGhlIGhpZGRlbiBsYXllciBieSBtdWx0aXBseWluZyB0aGUgaW5wdXQgZmVhdHVyZXMgd2l0aCB0aGUgd2VpZ2h0cyBjb25uZWN0aW5nIHRoZSBpbnB1dCBsYXllciB0byB0aGUgaGlkZGVuIGxheWVyLiBMZXQncyBkZW5vdGUgdGhlIGlucHV0IGZlYXR1cmVzIGFzIFwoIFxtYXRoYmZ7WH0gXCkgYW5kIHRoZSB3ZWlnaHRzIGJldHdlZW4gdGhlIGlucHV0IGFuZCBoaWRkZW4gbGF5ZXJzIGFzIFwoIFxtYXRoYmZ7V197XHRleHR7aW5wdXRcX2hpZGRlbn19fSBcKS4KCk1hdGhlbWF0aWNhbGx5LCB0aGlzIGNhbiBiZSByZXByZXNlbnRlZCBhczoKClxbIFxtYXRoYmZ7SF97XHRleHR7aW5wdXR9fX0gPSBcbWF0aGJme1h9IFx0aW1lcyBcbWF0aGJme1dfe1x0ZXh0e2lucHV0XF9oaWRkZW59fX0gXF0KCndoZXJlOgotIFwoIFxtYXRoYmZ7WH0gXCkgaXMgYSAxeDMgbWF0cml4IChpbnB1dCBmZWF0dXJlcykuCi0gXCggXG1hdGhiZntXX3tcdGV4dHtpbnB1dFxfaGlkZGVufX19IFwpIGlzIGEgM3g0IG1hdHJpeCAod2VpZ2h0cyBiZXR3ZWVuIGlucHV0IGFuZCBoaWRkZW4gbGF5ZXJzKS4KLSBcKCBcbWF0aGJme0hfe1x0ZXh0e2lucHV0fX19IFwpIHdpbGwgYmUgYSAxeDQgbWF0cml4IChpbnB1dCB0byBoaWRkZW4gbGF5ZXIpLgpgYGB7cn0KIyBGZWVkZm9yd2FyZCBwcm9jZXNzCmhpZGRlbl9pbnB1dCA8LSBpbnB1dHMgJSolIHdlaWdodHNfaW5wdXRfaGlkZGVuCmhpZGRlbl9vdXRwdXQgPC0gc2lnbW9pZChoaWRkZW5faW5wdXQpCnByaW50KCJPdXRwdXQgb2YgaGlkZGVuIGxheWVyIChhZnRlciBhY3RpdmF0aW9uKToiKQpwcmludChoaWRkZW5fb3V0cHV0KQpgYGAKIyMjIEZlZWRmb3J3YXJkIFByb2Nlc3M6IE91dHB1dCBMYXllciBDb21wdXRhdGlvbgoKSW4gdGhpcyBzZWN0aW9uLCB3ZSB3aWxsIGNvbXB1dGUgdGhlIGlucHV0IHRvIHRoZSBvdXRwdXQgbGF5ZXIgYW5kIHRoZW4gYXBwbHkgdGhlIHNpZ21vaWQgYWN0aXZhdGlvbiBmdW5jdGlvbiB0byBvYnRhaW4gdGhlIGZpbmFsIG91dHB1dCBvZiB0aGUgbmV1cmFsIG5ldHdvcmsuCgojIyMjIFN0ZXAgMzogQ29tcHV0ZSBJbnB1dCB0byBPdXRwdXQgTGF5ZXIKClRoZSBpbnB1dHMgdG8gdGhlIG91dHB1dCBsYXllciBhcmUgY29tcHV0ZWQgYnkgcGVyZm9ybWluZyBtYXRyaXggbXVsdGlwbGljYXRpb24gYmV0d2VlbiB0aGUgb3V0cHV0cyBmcm9tIHRoZSBoaWRkZW4gbGF5ZXIgYW5kIHRoZSB3ZWlnaHRzIGNvbm5lY3RpbmcgdGhlIGhpZGRlbiBsYXllciB0byB0aGUgb3V0cHV0IGxheWVyLgoKTWF0aGVtYXRpY2FsbHksIHRoaXMgaXMgcmVwcmVzZW50ZWQgYXM6CgpcWyBcbWF0aGJme1lfe1x0ZXh0e2lucHV0fX19ID0gXG1hdGhiZntIX3tcdGV4dHtvdXRwdXR9fX0gXHRpbWVzIFxtYXRoYmZ7V197XHRleHR7aGlkZGVuXF9vdXRwdXR9fX0gXF0KCndoZXJlOgotIFwoIFxtYXRoYmZ7SF97XHRleHR7b3V0cHV0fX19IFwpIGlzIHRoZSAxeDQgbWF0cml4IG9mIG91dHB1dHMgZnJvbSB0aGUgaGlkZGVuIGxheWVyIGFmdGVyIHRoZSBhY3RpdmF0aW9uIGZ1bmN0aW9uLgotIFwoIFxtYXRoYmZ7V197XHRleHR7aGlkZGVuXF9vdXRwdXR9fX0gXCkgaXMgdGhlIDR4MiBtYXRyaXggb2Ygd2VpZ2h0cyBiZXR3ZWVuIHRoZSBoaWRkZW4gbGF5ZXIgYW5kIHRoZSBvdXRwdXQgbGF5ZXIuCi0gXCggXG1hdGhiZntZX3tcdGV4dHtpbnB1dH19fSBcKSBpcyB0aGUgcmVzdWx0aW5nIDF4MiBtYXRyaXggb2YgaW5wdXRzIHRvIHRoZSBvdXRwdXQgbGF5ZXIgbm9kZXMuCgpgYGB7ciBjb21wdXRlLWhpZGRlbi1pbnB1dHMsIGVjaG89VFJVRX0KIyBDb21wdXRlIGlucHV0IHRvIG91dHB1dCBsYXllcgpmaW5hbF9pbnB1dCA8LSBoaWRkZW5fb3V0cHV0ICUqJSB3ZWlnaHRzX2hpZGRlbl9vdXRwdXQKZmluYWxfb3V0cHV0IDwtIHNpZ21vaWQoZmluYWxfaW5wdXQpCnByaW50KCJPdXRwdXQgb2YgZmluYWwgbGF5ZXIgKGFmdGVyIGFjdGl2YXRpb24pOiIpCnByaW50KGZpbmFsX291dHB1dCkKYGBgCiMjIyBBc3N1bWUgRXhwZWN0ZWQgT3V0cHV0CgpJbiBvcmRlciB0byBldmFsdWF0ZSB0aGUgcGVyZm9ybWFuY2Ugb2Ygb3VyIG5ldXJhbCBuZXR3b3JrLCB3ZSBuZWVkIHRvIGNvbXBhcmUgaXRzIHByZWRpY3Rpb25zIHRvIHRoZSBhY3R1YWwgZXhwZWN0ZWQgb3V0cHV0LiBUaGlzIHByb2Nlc3MgaXMgZXNzZW50aWFsIGR1cmluZyB0cmFpbmluZywgYXMgaXQgcHJvdmlkZXMgdGhlIGJhc2lzIGZvciBjYWxjdWxhdGluZyBlcnJvcnMgYW5kIHN1YnNlcXVlbnRseSB1cGRhdGluZyB0aGUgd2VpZ2h0cyB0aHJvdWdoIGJhY2twcm9wYWdhdGlvbi4KCiMjIyMgRGVmaW5pbmcgdGhlIEV4cGVjdGVkIE91dHB1dAoKRm9yIHRoaXMgZGVtb25zdHJhdGlvbiwgbGV0J3MgYXNzdW1lIHRoZSBleHBlY3RlZCBvdXRwdXQgb2Ygb3VyIG5ldXJhbCBuZXR3b3JrLiBUaGUgZXhwZWN0ZWQgb3V0cHV0IHNlcnZlcyBhcyB0aGUgZ3JvdW5kIHRydXRoIGFnYWluc3Qgd2hpY2ggd2Ugd2lsbCBtZWFzdXJlIHRoZSBuZXR3b3JrJ3MgcGVyZm9ybWFuY2UuCgpUaGUgZm9sbG93aW5nIFIgY29kZSBkZWZpbmVzIGEgc2ltcGxlIGV4cGVjdGVkIG91dHB1dCBtYXRyaXguIEluIHRoaXMgZXhhbXBsZSwgbGV0J3MgYXNzdW1lIHRoZSBleHBlY3RlZCBvdXRwdXQgZm9yIG91ciBzaW5nbGUgaW5wdXQgZXhhbXBsZSBpcyBcKCBbMCwgMV0gXCkuCgpgYGB7ciAgZGVmaW5lLWV4cGVjdGVkLW91dHB1dCwgZWNobz1UUlVFfQojIEFzc3VtZSBleHBlY3RlZCBvdXRwdXQKZXhwZWN0ZWRfb3V0cHV0IDwtIG1hdHJpeChjKDAsIDEpLCBucm93ID0gMSkKCnByaW50KCJBc3N1bWVkIGV4cGVjdGVkIG91dHB1dDoiKQpwcmludChleHBlY3RlZF9vdXRwdXQpCmBgYAojIyMgQ2FsY3VsYXRlIEVycm9yIG9mIHRoZSBPdXRwdXQKCkluIHRoaXMgc3RlcCwgd2UgY2FsY3VsYXRlIHRoZSBlcnJvciBvZiB0aGUgb3V0cHV0IG9mIHRoZSBuZXVyYWwgbmV0d29yay4gVGhpcyBlcnJvciByZXByZXNlbnRzIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIHByZWRpY3RlZCBvdXRwdXQgZ2VuZXJhdGVkIGJ5IHRoZSBuZXVyYWwgbmV0d29yayBhbmQgdGhlIGV4cGVjdGVkIChncm91bmQgdHJ1dGgpIG91dHB1dC4gTWVhc3VyaW5nIHRoaXMgZXJyb3IgaXMgYSBjcml0aWNhbCBwYXJ0IG9mIHRoZSB0cmFpbmluZyBwcm9jZXNzLCBhcyBpdCBwcm92aWRlcyB0aGUgaW5mb3JtYXRpb24gbmVlZGVkIHRvIGFkanVzdCB0aGUgbmV0d29yaydzIHdlaWdodHMgdG8gaW1wcm92ZSBhY2N1cmFjeS4KCiMjIyMgRXJyb3IgQ2FsY3VsYXRpb24KClRoZSBlcnJvciBpcyBjb21wdXRlZCBhcyB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBleHBlY3RlZCBvdXRwdXQgYW5kIHRoZSBhY3R1YWwgb3V0cHV0IHByb2R1Y2VkIGJ5IHRoZSBuZXVyYWwgbmV0d29yay4gTWF0aGVtYXRpY2FsbHksIHRoaXMgY2FuIGJlIHJlcHJlc2VudGVkIGFzOgoKXFsgXHRleHR7RXJyb3J9ID0gXG1hdGhiZntZX3tcdGV4dHtleHBlY3RlZH19fSAtIFxtYXRoYmZ7WV97XHRleHR7b3V0cHV0fX19IFxdCgp3aGVyZToKLSBcKCBcbWF0aGJme1lfe1x0ZXh0e2V4cGVjdGVkfX19IFwpIGlzIHRoZSBtYXRyaXggb2YgZXhwZWN0ZWQgKGdyb3VuZCB0cnV0aCkgb3V0cHV0cy4KLSBcKCBcbWF0aGJme1lfe1x0ZXh0e291dHB1dH19fSBcKSBpcyB0aGUgbWF0cml4IG9mIGFjdHVhbCBvdXRwdXRzIHByb2R1Y2VkIGJ5IHRoZSBuZXVyYWwgbmV0d29yay4KCmBgYHtyfQojIENhbGN1bGF0ZSBlcnJvciBvZiB0aGUgb3V0cHV0Cm91dHB1dF9lcnJvciA8LSBleHBlY3RlZF9vdXRwdXQgLSBmaW5hbF9vdXRwdXQKcHJpbnQoIk91dHB1dCBlcnJvcjoiKQpwcmludChvdXRwdXRfZXJyb3IpCmBgYAojIyMgQmFja3Byb3BhZ2F0aW9uIFByb2Nlc3MKCkluIHRoZSBiYWNrcHJvcGFnYXRpb24gcHJvY2Vzcywgd2UgY2FsY3VsYXRlIHRoZSBlcnJvciBhbmQgdXBkYXRlIHRoZSB3ZWlnaHRzIHRvIG1pbmltaXplIHRoaXMgZXJyb3IuIFRoaXMgcHJvY2VzcyBpcyBlc3NlbnRpYWwgZm9yIHRyYWluaW5nIHRoZSBuZXVyYWwgbmV0d29yay4KCiMjIyMgQ2FsY3VsYXRpbmcgRGVsdGEgZm9yIHRoZSBPdXRwdXQgTGF5ZXIKClRoZSBmaXJzdCBzdGVwIGluIGJhY2twcm9wYWdhdGlvbiBpcyB0byBjb21wdXRlIHRoZSBkZWx0YSAoZ3JhZGllbnQpIGZvciB0aGUgb3V0cHV0IGxheWVyLiBUaGUgZGVsdGEgcmVwcmVzZW50cyB0aGUgZXJyb3IgdGVybSBhZGp1c3RlZCBieSB0aGUgZGVyaXZhdGl2ZSBvZiB0aGUgYWN0aXZhdGlvbiBmdW5jdGlvbi4gRm9yIHRoZSBzaWdtb2lkIGFjdGl2YXRpb24gZnVuY3Rpb24sIHRoZSBkZXJpdmF0aXZlIGlzOgoKXFsgz4MnKHgpID0gz4MoeCkgXGNkb3QgKDEgLSDPgyh4KSkgXF0KClRoZSBkZWx0YSBmb3IgdGhlIG91dHB1dCBsYXllciBjYW4gYmUgY29tcHV0ZWQgYXM6CgpcWyBcZGVsdGFfe1x0ZXh0e291dHB1dH19ID0gXHRleHR7b3V0cHV0XF9lcnJvcn0gXGNkb3Qgz4MnKFxtYXRoYmZ7WV97XHRleHR7b3V0cHV0fX19KSBcXQoKd2hlcmU6Ci0gXCggXHRleHR7b3V0cHV0XF9lcnJvcn0gXCkgaXMgdGhlIGVycm9yIG9mIHRoZSBvdXRwdXQgY29tcHV0ZWQgZWFybGllci4KLSBcKCDPgycoXG1hdGhiZntZX3tcdGV4dHtvdXRwdXR9fX0pIFwpIGlzIHRoZSBkZXJpdmF0aXZlIG9mIHRoZSBzaWdtb2lkIGZ1bmN0aW9uIGFwcGxpZWQgdG8gdGhlIG91dHB1dCBsYXllciB2YWx1ZXMuCgpgYGB7ciBjYWxjdWxhdGUtZGVsdGEtb3V0cHV0LCBlY2hvPVRSVUV9CiMgRGVmaW5lIHRoZSBkZXJpdmF0aXZlIG9mIHRoZSBzaWdtb2lkIGZ1bmN0aW9uCnNpZ21vaWRfZGVyaXZhdGl2ZSA8LSBmdW5jdGlvbih4KSB7CiAgeCAqICgxIC0geCkKfQoKIyBDYWxjdWxhdGUgdGhlIGRlbHRhIGZvciB0aGUgb3V0cHV0IGxheWVyCmRfb3V0cHV0IDwtIG91dHB1dF9lcnJvciAqIHNpZ21vaWRfZGVyaXZhdGl2ZShmaW5hbF9vdXRwdXQpCnByaW50KCJEZWx0YSBmb3IgdGhlIG91dHB1dCBsYXllcjoiKQpwcmludChkX291dHB1dCkKYGBgCgojIyMgVXBkYXRlIFdlaWdodHM6IEhpZGRlbiB0byBPdXRwdXQgTGF5ZXIKCkFmdGVyIGNhbGN1bGF0aW5nIHRoZSBkZWx0YXMgZm9yIHRoZSBvdXRwdXQgbGF5ZXIgaW4gdGhlIGJhY2twcm9wYWdhdGlvbiBwcm9jZXNzLCB3ZSBwcm9jZWVkIHRvIHVwZGF0ZSB0aGUgd2VpZ2h0cyBjb25uZWN0aW5nIHRoZSBoaWRkZW4gbGF5ZXIgdG8gdGhlIG91dHB1dCBsYXllci4gVGhlIHdlaWdodCB1cGRhdGUgcHJvY2VzcyBhaW1zIHRvIG1pbmltaXplIHRoZSBlcnJvciBpbiB0aGUgbmV0d29yayBieSBhZGp1c3RpbmcgdGhlIHdlaWdodHMgYmFzZWQgb24gdGhlIGNhbGN1bGF0ZWQgZGVsdGFzLgoKIyMjIyBXZWlnaHQgVXBkYXRlIFByb2Nlc3MKClVzaW5nIHRoZSBjb21wdXRlZCBkZWx0YXMgKFwoIFxkZWx0YV97XHRleHR7b3V0cHV0fX0gXCkpLCB3ZSBhZGp1c3QgdGhlIHdlaWdodHMgYmV0d2VlbiB0aGUgaGlkZGVuIGFuZCBvdXRwdXQgbGF5ZXJzLiBUaGUgd2VpZ2h0IHVwZGF0ZSBydWxlIGZvciBncmFkaWVudCBkZXNjZW50IGlzIGFzIGZvbGxvd3M6CgpcWyBcdGV4dHtOZXcgV2VpZ2h0fSA9IFx0ZXh0e09sZCBXZWlnaHR9ICsgXGV0YSBcY2RvdCAoXG1hdGhiZntIX3tcdGV4dHtvdXRwdXR9fX1eVCBcY2RvdCBcZGVsdGFfe1x0ZXh0e291dHB1dH19KSBcXQoKd2hlcmU6Ci0gXCggXGV0YSBcKSBpcyB0aGUgbGVhcm5pbmcgcmF0ZSwgY29udHJvbGxpbmcgdGhlIHN0ZXAgc2l6ZSBvZiB3ZWlnaHQgdXBkYXRlcy4KLSBcKCBcbWF0aGJme0hfe1x0ZXh0e291dHB1dH19fV5UIFwpIGlzIHRoZSB0cmFuc3Bvc2Ugb2YgdGhlIGhpZGRlbiBsYXllciBvdXRwdXQgbWF0cml4LgotIFwoIFxkZWx0YV97XHRleHR7b3V0cHV0fX0gXCkgaXMgdGhlIGRlbHRhIGZvciB0aGUgb3V0cHV0IGxheWVyLgoKYGBge3IgdXBkYXRlLXdlaWdodHMtaGlkZGVuLW91dHB1dCwgZWNobz1UUlVFfQojIERlZmluZSB0aGUgbGVhcm5pbmcgcmF0ZSBmb3Igd2VpZ2h0IHVwZGF0ZXMKbGVhcm5pbmdfcmF0ZSA8LSAwLjUKCiMgVXBkYXRlIHRoZSB3ZWlnaHRzIGJldHdlZW4gaGlkZGVuIGFuZCBvdXRwdXQgbGF5ZXJzCndlaWdodHNfaGlkZGVuX291dHB1dCA8LSB3ZWlnaHRzX2hpZGRlbl9vdXRwdXQgKyB0KGhpZGRlbl9vdXRwdXQpICUqJSBkX291dHB1dCAqIGxlYXJuaW5nX3JhdGUKCnByaW50KCJVcGRhdGVkIHdlaWdodHMgYmV0d2VlbiBoaWRkZW4gYW5kIG91dHB1dCBsYXllcjoiKQpwcmludCh3ZWlnaHRzX2hpZGRlbl9vdXRwdXQpCmBgYAojIyMgQ29uY2x1c2lvbjogSW50ZXJwcmV0YXRpb24gb2YgT3V0cHV0IEVycm9yCgpJbiB0aGUgbmV1cmFsIG5ldHdvcmsgY29udGV4dCwgdGhlICJPdXRwdXQgZXJyb3I6IiBtYXRyaXggY29udmV5cyB0aGUgZGlzcGFyaXRpZXMgYmV0d2VlbiB0aGUgcHJlZGljdGVkIG91dHB1dCB2YWx1ZXMgZ2VuZXJhdGVkIGJ5IHRoZSBuZXR3b3JrIGFuZCB0aGUgYWN0dWFsIGV4cGVjdGVkIG91dHB1dCB2YWx1ZXMuIFVuZGVyc3RhbmRpbmcgYW5kIGFuYWx5emluZyB0aGVzZSBvdXRwdXQgZXJyb3JzIGFyZSBmdW5kYW1lbnRhbCB0byBldmFsdWF0aW5nIHRoZSBuZXR3b3JrJ3MgcGVyZm9ybWFuY2UgYW5kIGd1aWRpbmcgdGhlIHRyYWluaW5nIHByb2Nlc3MgdG93YXJkcyBvcHRpbWl6YXRpb24uCgojIyMjIEFuYWx5c2lzIG9mIE91dHB1dCBFcnJvciBWYWx1ZXMKCi0gKipOZWdhdGl2ZSBFcnJvciAoQ29sdW1uIDEpOioqCiAgLSBUaGUgbmVnYXRpdmUgdmFsdWUgb2YgYXBwcm94aW1hdGVseSAtMC43NzU4NjQ5IHN1Z2dlc3RzIGFuIHVuZGVyZXN0aW1hdGlvbiBieSB0aGUgbmV1cmFsIG5ldHdvcmsgaW4gcHJlZGljdGluZyB0aGUgY29ycmVzcG9uZGluZyB0YXJnZXQgb3IgY2xhc3MuIFRoZSBsYXJnZXIgdGhlIG1hZ25pdHVkZSBvZiB0aGUgbmVnYXRpdmUgZXJyb3IsIHRoZSBtb3JlIHNpZ25pZmljYW50IHRoZSB1bmRlcmVzdGltYXRpb24gcmVsYXRpdmUgdG8gdGhlIGFjdHVhbCBleHBlY3RlZCBvdXRwdXQuCgotICoqUG9zaXRpdmUgRXJyb3IgKENvbHVtbiAyKToqKgogIC0gVGhlIHBvc2l0aXZlIHZhbHVlIG9mIGFyb3VuZCAwLjEwMTIwMDYgcmV2ZWFscyBhbiBvdmVyZXN0aW1hdGlvbiBpbiB0aGUgbmV0d29yaydzIHByZWRpY3Rpb25zIGZvciB0aGUgY29ycmVzcG9uZGluZyB0YXJnZXQgb3IgY2xhc3MuIFRoZSBtYWduaXR1ZGUgb2YgdGhlIHBvc2l0aXZlIGVycm9yIGluZGljYXRlcyB0aGUgZGVncmVlIG9mIG92ZXJlc3RpbWF0aW9uIHJlbGF0aXZlIHRvIHRoZSBncm91bmQgdHJ1dGguCgojIyMjIEluc2lnaHQgZm9yIFRyYWluaW5nIGFuZCBPcHRpbWl6YXRpb24KCi0gKipFcnJvciBNaW5pbWl6YXRpb246KioKICAtIE1pbmltaXppbmcgdGhlIG91dHB1dCBlcnJvciBpcyB0aGUgbWFpbiBvYmplY3RpdmUgZHVyaW5nIHRyYWluaW5nLiBUZWNobmlxdWVzIGxpa2UgYmFja3Byb3BhZ2F0aW9uIGFuZCB3ZWlnaHQgYWRqdXN0bWVudHMgcmVkdWNlIHRoZXNlIGVycm9ycywgYWxpZ25pbmcgdGhlIG5ldHdvcmsncyBwcmVkaWN0aW9ucyBtb3JlIGNsb3NlbHkgd2l0aCB0aGUgZXhwZWN0ZWQgb3V0cHV0cyBhbmQgaW1wcm92aW5nIGl0cyBvdmVyYWxsIGFjY3VyYWN5LgoKLSAqKkd1aWRpbmcgTmV0d29yayBJbXByb3ZlbWVudDoqKgogIC0gQW5hbHl6aW5nIGFuZCBtb25pdG9yaW5nIHRoZSBvdXRwdXQgZXJyb3IgdmFsdWVzIHByb3ZpZGVzIGluc2lnaHRzIGludG8gdGhlIG5ldHdvcmsncyBwZXJmb3JtYW5jZSwgZW5hYmxpbmcgaXRlcmF0aXZlIGFkanVzdG1lbnRzIHRvIGVuaGFuY2UgcHJlZGljdGlvbiBxdWFsaXR5LiBVbmRlcnN0YW5kaW5nIHRoZSBlcnJvciBwYXR0ZXJucyBoZWxwcyBpbiBpZGVudGlmeWluZyBhcmVhcyBmb3IgcmVmaW5lbWVudCBhbmQgb3B0aW1pemluZyB0aGUgbmV1cmFsIG5ldHdvcmsncyBsZWFybmluZyBwcm9jZXNzLgoKSW4gY29uY2x1c2lvbiwgdGhlIGludGVycHJldGF0aW9uIG9mIG91dHB1dCBlcnJvciB2YWx1ZXMgc2VydmVzIGFzIGEgbWV0cmljIGluIGFzc2Vzc2luZyB0aGUgbmV1cmFsIG5ldHdvcmsncyBwcmVkaWN0aXZlIHBlcmZvcm1hbmNlIGFuZCByZWZpbmluZyBpdHMgYWNjdXJhY3kuIEJ5IG1pbmltaXppbmcgdGhlc2UgZXJyb3JzIHRocm91Z2ggdGFyZ2V0ZWQgb3B0aW1pemF0aW9uIHN0cmF0ZWdpZXMsIHRoZSBuZXR3b3JrJ3MgcHJlZGljdGl2ZSBjYXBhYmlsaXRpZXMgYmVjb21lIG1vcmUgcmVsaWFibGUgYW5kIHByZWNpc2UgcHJlZGljdGlvbnMuCg==